I've had my N800 for only a few days now, but I haven't seen this issue with Skype that you're describing.

After I installed it (OS 2008 btw), no one in my contact list was online. I called the echo test contact and that all worked good. Last night I finally had a chance to use the voice chat feature and it worked perfectly without having to do the test call thing.

So maybe the test call is required at least once?