Looks like Skype has released a full version of their VoIP client for Android phones, but sadly it’s WiFi only if you’re in the US—but at least it is now widely available.
You can sync your Skype friends with your contacts on the phone, and chat with multiple people at once, and obviously place calls to other Skype users and regular phones. You’ll find Skype on the Android market, or you can head to skype.com/m on your phone, but keep in mind that it only works for Android 2.1 or 2.2 devices so it won’t be available otherwise.
Here’s a video that shows how it all works:
Skype [The Big Blog]