Always depends on what the overall ambience and feel should be of course. What type of game is it?
I really enjoy the iPhone games that are on the app store, all of them have very nice menu sounds. Like the Halfbrick Studio games, Fruit Ninja for example. One interface (and overall sound in game btw) I really liked was "Bulletstorm". I know that isn't helping but it could be something to be inspired by.
I've never actually (professionally) worked with games and sound design for HUDs and menus, but I'd like to think that if I were, I'd work with the imagery and overall feel. I mean if the game's all about cowboys I'd work with leather, chains and the likes. If the game's about dancing I'd probably want to manufacture some music-like sounds. Small snippets.
In a way I think the easiest route to go is to make it simple and start out with finding small snippets of sound with only one object. Set creative boundaries for yourself.
Sort of like Diego Stocco making music out of just one thing, that trick could be really creatively inspiring.
I remember doing sound design for a short film in the beginning of my career, and the film contained a computer like thingy that had to have interaction sounds. The thingy was to look old and crappy, so I decided that I would use a printer and record all different stages of that and cut out small snippets of the printer sounds. That way, I had just used one "thing" to make the sound for the computer thingy. That made it simple, and it made it fun.
That's what I do when I run out of ideas anyway.
I'm sure you'll come up with something and it will rock!