As of a few days ago, foursquare venues/search with intent=browse seems to ignore categoryId. It definitely worked before that. If I change intent=checkin the category filtering is applied. Here's a sample query
https://api.foursquare.com/v2/venues/search?radius=1405&ll=37.769587%2C-122.420139&limit=30&intent=browse&client_id=CLIENTID&v=20120216&client_secret=CLIENTSECRET&categoryId=4d4b7105d754a06374d81259
note I'm doing a userless query. Perhaps related to the recent changes to allow multiple categoryId's?