I mentioned in my previous response that I reset my hearthstone at the innkeeper, and didn't have this issue again.
Well I was able to get by for about three weeks. Then in Uldum... again. There's no portal back to Org or SW in Uldum, so you really have no choice but to hearth or fly.
After my hearthstone failed this last time I took a flight straight to ORG and bought "Cloak of Coordination" from the guild vendor. It's my backup, cause this hearthstone issue is just stupid nuts.
A friend/fellow pet collector says his mage portals often fail on the first use, after battling pet tamers. It goes through the loading screen and then duds out. But fortunately mages can just re-click a portal. Hearthstones have a cooldown, and you're just stranded!
I hope someone from Blizzard has been directed to this post, because no, it's not an isolated issue. And you can guarantee that for the few who have posted here about the issue, there are MANY who are having the problem who don't come on this forum, and don't submit in-game tickets. But this needs to be fixed. Apparently the blizz rep who responded that no one else is having this issue, doesn't do any pet tamers.
In the meantime, I recommend that people go to their guild vendor and get a "Cloak of Coordination."
There is also a rather extensive list of items that teleport in the comments on wowhead under "Jaina's Locket".http://www.wowhead.com/item=52251#comments