Given that the movie takes place during the reign of Richard I, all the characters should be speaking Early Middle English, something of a transitional period between Beowulf and Chaucer. With this in mind, the other actors' modern English accents aren't really any more "correct" than Costner and Slater's American ones. (And it'd be nearly impossible to duplicate an Anglo-Norman accent anyway, since the language probably didn't sound much like modern French at all. Why try?)
Many linguists theorize that the American accent actually is the original British accent.
Furthermore, as part of the Anglo-Norman aristocracy, Robin may not have spoken English: Norman French was the language of the English nobility of the time, and in fact Richard himself didn't speak English at all.
Why were they even speaking with the same accent in the first place (apart from the obvious explanation)? Your accent is set by listening to your parents speech, how the people around you talk, and the area you grew up in, though it is possible to lose an accent or for it to change over time, that would only be if you move to a different geographic area, and know what that other accent sounds like, so you can pick it up. Will knows who Robin is presumably from what his Mother has told him, and from stories he has heard about him, however Robin has no idea who Will is until they meet for the first time by the river, and even then he doesnt know who he really is until near the end of the movie. This suggests that they didnt grow up on the same estate or even the same town. The rest of Merry Men, who are presumably all from the areas local to Sherwood Forest, dont speak with same accent either (They do, however, speak with the full gamut of English regional accents, due the British actors themselves speaking with their own natural voices, but thats probably a for different discussion ), so how on earth did Will end up with the same accent as Robin if they didnt grow up together, and never knew each other, and Will only had very limited contact, if any at all, with their shared father, who also didnt speak with the same accent, and had no contact with anyone else who spoke like that (Since there is no suggestion that his mother had the same accent, and Robin's accent would have been set way before she was on the scene anyway)?
The Sheriff and his cousin, Guy of Gisbourne, both eye-rolling when the Bishop asks for God's blessings on the Sheriff? The Sheriff is a devil worshiper (and so is his cousin, possibly).
In the extended version of the movie, we learn a little about the Sheriff of Nottingham's parentage. The witch Mortianna herself was his mother, and she killed a baby in the palace so that she could substitute her baby in his place. This brings up a number of horrific implications.
Probably one of the most subtle is shown when Mortianna talks about how she has been seen as a freak all of her life. Given that, how did she become pregnant? Considering her lack of sympathy for Marian's plight, it is likely that the Sheriff is the product of rape, perhaps even rape by a nobleman... in which case, having her son produce the heir to the throne by raping a nobleman's daughter is the ultimate act of revenge.
This also explains why the Sheriff, upon demanding a "proper" wedding to Maid Marian, snarls that "I will not take her until we are properly wed! For once in my life, I will have something pure!"
This is also Fridge Brilliance as well. Had the Sheriff simply raped Marian without being married in a Christian ceremony first, the resulting child would simply be a bastard, and therefore would not be eligible to ascend to the throne. The pair's plan all along was for the Sheriff to marry Marian, father a son, use her royal blood as part of a coup to take the throne, (possibly) kill her off, and rule as regent in his son's name.
Mortiana's plan on how she got her baby to become the Sheriff of Nottingham in the first place also wanders into Fridge Logic if you know anything about how the Medieval Sheriff's were appointed. The movie suggests that Nottingham got his position because he inherited it via his family, but becoming a Sheriff in England has never been an inherited title - you had to be appointed by the King from a shortlist of names that was given to him by an Tribunal, who had chosen them from a much longer list of suitable candidates, meaning that he had to be recommended to begin with, though admittedly, this could be open to corruption and abuse, but even if they did that, then it was not guaranteed that he would get the role from the King. So Mortiana could had gone through all that will no chance of her plan actually succeeding in the first place. Maybe she thought that the baby swap into a family with a good name was the only way it could happen, with her manipulating things behind the scenes. Even then, the movie never explains how she thought that making her son become a civil servant would have helped her cause in the first place. Also, her and the Sheriff's plan to try and seize the Crown of England is not well thought out - there were already many more legitimate (including a brother and nephew) claims before any would be child's of Marian would have ever been considered, unless they were planning of murdering everyone of them, at which point you would think someone would notice something suspicious was going on after the first few had died. This could have also led to a long drawn out war with other families, and countries (Some French Duke's would have had just a good a claim.), which many a disputed claim to the crown has caused, that they may not have even won. If Mortiana was that desperate to get her bloodline on the throne, then why didnt she just swap her baby with a baby that had connections to the actual Royal family, then use that claim to take the crown, instead of trying to get him to marry a distant relative of the King, who was nowhere near the line of succession?