I have installed skype on my fresh squeeze 64bit system. It works fine except for the fact that the gtk theme isn't really working and the result is quite ugly:

How can I fix this?
Skype is a proprietary 32-bit application, and cannot use 64-bit Gtk+ theme engines.
Try installing ia32-libs-gtk, which provides several engines. If that doesn't work, you'll have to change themes so that you are using an engine which is available in 32-bit.
ia32-libs-gtk installed as I thought it would make gtk available to 32bit applications, but skype doesn't seem to care use export GTK2_RC_FILES="/etc/gtk-2.0/gtkrc:$HOME/.gtkrc-2.0"
You can put this in your ~/.bashrc so it is always available.
Also, try this: run qtconfig and choose GTK+ as the theme for qt applications.
ephemient's idea is intriguing. Try installing other GTK engines and switching to them to see whether Skype is able to use the new ones without falling back to Raleigh. I know it sounds nightmarish, but you can also run Skype under strace and see what files it fails to open (if any). Also, what engine are you using? Gnome/GTK 2 or 3?
As another data point, I'm running it under Ubuntu 11.10 64-bit with Unity and Radiosity and it picks up the engine correctly.
A final note: I would comment on epemient's answer, but I suffer from low karma here. :-(