UART can't run at higher baud rates

I have a design (EP2C8) where I am using the UART in the SOPC system, and when we set the baud rate above 9600 or so, we start having corruption issues. It is very strange, since we had a similar design a couple years ago, and didn't have this issue. I have connected TXD to RXD outside of the SOPC system and verified the physical connections, so I can only conclude that it is inside the SOPC system. We don't use CTS and RTS, but neither did the original system. The software engineer says it is the same code as before.

Has anyone ever run into this issue?

Thanks,

Mark