I know the following steps will reproduce it, but there may be other ways to do it as well:
1) Select "All Photographs"
2) Go to Map module and find a location that has at least one photo
3) Select "Visible on Map"
4) go back to Library
5) quit and restart lightroom
6) change filters to some other set (Default Columns will work)
7) select a filter on anything
You will now see a set of pictures that doesn't match what the filters describe because Lightroom is still applying the "Current Map Location" filter, it's just not showing it to you. The only way I have found to get rid of that filter is either to go back to the Map module and click "None" on the filter bar or to change the metadata columns to put "Map Location" first and switch it back to "All"
I suspect this is the cause of the "Filters not working" thread on the LR4b forum that never got resolved.
That does sound like a plausible culprit. Please repost this on the feedback forum, where Adobe wants all bug reports: