Photoshop has some old 15 bit limitations in some of the implementations of its formats, and I know it prompts you with messages of "Images greater than 30,000 pixels on a side may be incompatible...".
Perhaps you've hit one of these limitations (I'm not sure about the PNG implementation, I haven't experimented with it specificially myself).
I do know that Adobe is aware of these limitations and that we've reached a time where computers are now big enough to easily handle gigapixel+ sized images.
Edit: Disregard - I see Chris has answered definitively in the time I took between reading your post and posting a response.
-Noel
