Also, it's not VoIP from the phone like Skype is. It uses your regular voice connection and voice minutes and not the data connection. What it does provide is a portable phone number, free SMS, voice mail transcriptions, and a host of other calling features. It's the kind of innovative application you'd expect when you combine the cloud with smartphone technology. Apple just doesn't want you to have it.
Unfortunately, back to your original comment about why apps are rejected (private apis, etc, etc) is, unfortunately for you, not true. Lets say you want an app to control your PC bittorrent app from your iPhone? -- Forget it, also not allowed. I understand now allowing apps that put strain on the network or use private apis but rejecting innovative apps or app that hurt Steve Jobs sense of morality just rubs me the wrong way. I'd rather have an open platform with a slower upgrade cycle.
It is a shame that they used "duplicate functionality" as the excuse, they should have just said "this is not acceptable under our AT&T plan".