HurtCow, google for Window Decorations in Ubuntu. Apparently this is an issue to several people. I must be lucky, because I have not had this issue come up on my boxes running Ubuntu, and I am currently running 9.04 with all little desktop effects that make Vista, and OSX drool.
Here is a link that should help.
gnome window borders missing - Ubuntu Forums