Skype is a popular VoIP application that has gained a reputation for working well on just about any internet connection (including a 56k dial-up modem!).
The main downside of Skype is that it is proprietary software and uses proprietary protocols and algorithms. However the authors do provide a Linux version compiled for many popular distributions.
Skype doesn't work in Ubuntu Hoary
See UbuntuNotes for some potential fixes.