It looks like the issue can be worked around by moving the maps out of the Downloads folder.
See this post on Team Liquid: http://www.teamliquid.net/forum/viewmessage.php?topic_id=130932
I moved my maps to /Documents/Blizzard/Starcraft II Beta/Maps and from there I can load all the ones I've tried.
I don't think there's anything special about that folder. It's just moving them out of system folders that's important.
Hope that helps the rest of you.