I expect there is a package for the 32-bit compatibility layer, but since I don't use a 64-bit processor I've not tried installing it. "Ubuntu skype 64" on Google turns up a number of links which will probably explain in some detail.
As for other programs, there are quite a number of them that support SIP, which is an open protocol (as opposed to Skype's, which is closed). Wikipedia has a list of SIP software
, which includes a number of Linux clients (as well as Windows). Ekiga and kphone are some of the better known ones, but there are several others. I'm afraid I haven't actually got round to setting up SIP myself, so I can't really give you any more detailed information.