For anybody reading this there is obviously some sort of network issue in the Hutt Valley which I am assuming is potentially more widespread. Currently it doesn't seem possible to send any SMS's while in 3G mode - switching your phone to GSM mode works fine... Bit of a whierd issue considering they both use the same SMSC.