Ekiga, formerly known as Gnomemeeting, is a Linux based softphone/videophone. (A newer version is also available for Windows). They’ve thought of everything… STUN, H.323, SIP, a directory, NAT traversal, you name it.
I’m using version 2.03 that was in the stock installation of Ubuntu Feisty. After a couple hours of fiddling, (at least 30 minutes of which was finding out that my microphone was switched off…) I’ve been able to make test voice calls to what sounds like their Asterisk server. Looking around, it says they are up to about 2.09, and if you want it work full-screen, you have to compile from the source code.