This is a very good question for /r/Latin, where you'll find people proficient at Classical and Medieval Latin.

A literate Roman would have been able to understand written Medieval or Renaissance Latin. Remember that people at these times were still reading classical texts, so they were familiar with the Latin from ~1500 years before. But changes in vocabulary, derivation and syntax meant that it would have sounded very clunky. I personally learnt Classical Latin and can go into a Medieval church or something and read the Latin on the gravestones etc fine. There are just lots of extraneous prepositions, the word order is different, and the words have changed a bit (canto instead of cano for 'sing', for instance).

I think there would have been a more significant language barrier in spoken Latin, however, depending on where in Europe the middle ages speaker lived.

It's also worth remembering that a 3rd century BC Roman would have spoken and written very differently from a AD 4th century Roman. This would affect the level of intelligibility substantially.