Are you going to choose multiple, then show then at random each time the menu is opened (similar to the loading screen), or are you just going to choose one? I personally think you should choose multiple so that it's not always the same.
I agree - the only potential pitfall I see is that too many menu backgrounds might take up too much space on the hard drive, so you probably couldn't have more than about 10 or so to choose from. Otherwise, I love the idea!
Maybe you could create a user setting so that they can choose whether to render a small cubemap at their current location or select one of a small number of default menu backgrounds.