Basically nothing. Just a different flavor of eye candy. KDE tends to focus a bit more on the posh-ness of the GUI; Gnome is typically 'cleaner' and more OCD in it's own way.
yes, but ubuntu has gnome utilities like gedit and other gnome-specific utilities, like the menu, and kubuntu has KDE stuff, like konqueror and the kde menu.