Hey OTH,
I'm in Australia and suffering the same problem. I was on the phone to support this morning as well and went through the same thing you did with the same result telling me to go to the Apple store, get a replacement and tell them I wanted it updated with the latest software.
So there I was at the main store in George Street, telling this guy what support had told me to do, with him telling me it wasn't there policy to update the software. After some gentle persuasion he went away but then came back and said they didn't have a micro usb in the store!!!
So I managed to get him to follow me down to the Apple TV display, where by the way their unit has the updated software, and got him to plug mine in instead and try the download. FAIL
So then they took the unit away into the back rooms, where they had discovered a micro usb. About ten minutes later they came back with the unit, download via iTunes - FAIL
So seeing my unit had been handled so much I took a brand new one home. So I wouldn't bother going into the store if I was you.
Tony