Cool - If you want us to investigate further (happy to), we need a destination phone number :-) Otherwise it's like shooting fish in a lake....
At least one of 2degrees' agents called the number and noticed it is a Skype dial in number, because it said "Welcome to Skype..., blah blah". Then another agent emailed me saying VOIP is not supported.
There is some irony given that 2 Degrees Broadband give out VoIP numbers on their service. :/
I have a Skype-to-Go service, but I can call local Skype number from all my 2degrees mobiles. This may suggest it has nothing to do with 2 degrees. The "number not recognised.." announcement likely comes from Skype not recognising the CALLING party number (ie. not registered with Skype). In you Skype service settings have you registered your mobile phone number (the CALLING mobile number you use to make Skype call)? Also try deleting the number and re-registering it again. Else try contacting Skype it may be problems on their end. This is a Skype security feature that allows only the valid Calling Party number(s) to access your Skype service, otherwise without CALLING number screening anyone calling 09 889XXXX will be connected to your overseas relative number.