As far as making it obvious goes, I was thinking in terms of Create Entries Beta: outline icon on hover, plus whatever else is already done to make it obvious when you can change a user icon. Parallel construction/method, and all that.

And, oh, hey! I just finally realized that when you do a custom mood the Create Entries Beta already already does pretty much what I described, except for being able to click directly on the icon to change it! *dopeslaps self*

I do think it would be better to keep your proposed button as "browse" rather than "change", though, if only for the people who choose more by images than words.