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.