Hmm, it shouldn't do that. Doesn't sound like the unlock was applied correctly. Try calling back and speaking with a different rep. It's possible they didn't do it right the first time.
They say it is unlocked - they know that the Truephone SIM won't work, the Global Roaming they don't know about but as I said it doesn't work either. Will test out another SIM card when I get to Australia.