Century Gothic is, last time I checked, a paid font: I tried to get it once and found I needed to purchase it. General rule, paid fonts aren't usually considered Web Safe.
Verdana is NOT on *nix machines unless users download msttcorefonts (which is free but you do have to go ahead and do the apt-get yourself). I have Verdana because I did download them (for Gimp).
I love Verdana but you have to be really careful with it due to its large-than-normal x-height. In fact, I try to only pair it with Bitstream Vera Sans and DejaVu Sans because they're also pretty big (so users who don't have Verdana may be Unix people with one of the other two). And if I have small fonts that are Verdana I'm uneasy because someone with none of those fonts will default to the system sans-serif, which would be too small for some people.
Definitely, it was a menu of mine where I first saw this: it was originally Verdana, Arial, Helvetica, sans-serif; and while things looked ok on my machine (back then I didn't have MS fonts), on a Windows machine the menu wrapped. That's when I got careful with Verdana : )
The menu does look like a font issue, so I will need to adjust for that. I know the clear:both fixed the Opera float issue on Windows, but I take it that it still looks wrong in Linux as per your screen shot.
I partially covered up the scrolly thing with that overflow problem, lemme post just a full plain screenshot.
http://stommepoes.nl/creativeopera.png (if it's 404 I haven't uploaded it yet, and it will be indexed so don't worry about banding colours)