Details: The text comes in from the right phone number, which shows as "+6421..." when you view message details. The outgoing message fails instantly with "Unable to send message after multiple attempts", and if you look at the message details the +64 prefix has been removed and nothing put back in its place.
I've tried entering the contact's number in several different ways but it doesn't seem to have fixed the problem yet. Creating a new text from scratch to the contact works fine. MMS seems to work OK, I've used the APN details from another thread on here to get that working.