Possibly, but as in the modern day it depends on the experience of the audience.

The joke works because, at the time when the film came out, almost every school in the UK taught some Latin and almost everyone had some experience of learning Latin. (As /u/umop_apisdin has commented with citation, most schools at the time did not offer Latin, I'm just from a posh place) language classes were quite widespread. In the scene, Brian is reprimanded for his bad Latin by the Roman soldier as if he were a student getting his work corrected, as the audience will remember from language classes back in school. The joke isn't that his Latin is bad, it's the response of the soldiers.

Would this joke have worked in the first century AD? That depends on who was in the audience.

The joke works best for people who have been taught languages by a teacher. For most Romans, this would only have taken place in early childhood, if at all. Most teaching in the Roman world was private, and most Romans could not afford a teacher. Many Romans went through the ludus litterarius, a cheap(ish) public class that taught basic reading and writing for children up to the age of 9 or 10, but it was rare to get education beyond that. The next stage of education was private tutoring by a grammaticus, who did teach the finer points of Latin and Greek. The elite could also hire a rhetor to teach public speaking, along with a more rounded education in philosophy, maths, music, and so on. People who had been taught by a grammaticus or rhetor would have had a vivid enough memory of being taught languages to find the joke in how the soldier's responded to Brian in the scene. That is a very small portion of Roman society.

Another problem with telling the joke in the 1st century AD is that Latin was a common first language. We don't think about the grammatical rules of English because we just know them. We've never been corrected on our use of the active or passive voice, for example, because that's just something we pick up. We don't even think about when we are using them. We do think about the different cases of Latin because it's something we've had to learn artificially. For people whose first language was Latin, the joke probably would not work as well because they would not have been as actively aware of their language's rules.

Many people in the provinces - Britannia, Gaul, Africa etc. - would have had a longer Latin education because their first language would most likely have been vernacular and basic Latin teaching was more organised. Tacitus tells us that Latin schools were set up in Britannia and Gaul to teach the locals, so the experience of getting their accusative and dative cases mixed up would have been more familiar to them, and they would have been more likely to get the joke.

The "Romans go home" routine would have worked in Lundinium, but would probably only get a chuckle in Pompeii.