Skype for Linux - closed beta test announced 05/16/04
Looks like you have to be a member of the Skype discussion forums, but registration is free I believe and I'm sure they could use some skilled Linux users. :)
Check out the announcement here
from the user terminus who is part of the Skype Staff.
And for the mods: yes I know there's a thread
about Skype (and possibly others too) and getting it to work under WINE but I feel that this would be off-topic for that thread since it's not related to running under WINE but running in Linux w/o WINE. :)