I use Totem to view my DVDs and anything web-related, so I can chime in and verify a similar situation.
Now that you mention it, I have just noticed the same problem on one of my machines that is fully updated with Level 3 packages. I do not use it often or I would have noticed this issue sooner. There is no DVD menu and the movie goes ahead and starts. To compound the issue, I have a green bar and rainbow banding on DVDs and WMA files in Firefox 3.03.
My main machine that has a basic Mint 5 install and ONLY updated with Level 1 and 2 packages is performing flawlessly. I have menus and excellent video with DVDs in Totem, as well as great quality playback in Firefox 3.03.
Upon further testing, I have discovered that the Mint 5 64-bit RC1 version has the same problem with not showing a DVD menu in the basic installation. As well, I am getting a green bar across the bottom of the Totem screen and some serious rainbow banding when playing WMA files in Firefox 3.03.
My concern is that there is some package update between the original Mint 5 32-bit release and the Mint 5 64-bit release candidate which is not sitting well with my systems. What is different that could be causing this issue? Certainly there are others who probably have this problem, but have not noticed.
While not an answer to your problem, I just wanted you to know that you were not a lone ranger. Husse or Clem probably already have some ideas, and there is most likely already a fix in the pipe. As for now, I know the original install with only Level 1 and 2 updates works great. It is those darned Level 3 packages that are so vexing.