Can you make your version of the game "work" with some other graphics, like squirrels or something, and provide an interface where users create and save their own images that will show up in the game? It might be a fun idea, like Make Your Own Opoly? I see lots of posts with individual interpretations about the look of a lemming... lots of variation there. So, maybe everyone's idea of the look of a lemming is different? Plus, people could just insert any images they happen to have laying around and it wouldn't be your responsibility what they choose. No ideas about sounds, but I think it might be fun to make my own lems to use.
Plus, when a person registers a trademark or applies for one, they have to register with someone, like the US Patent office I think??? Is that a place to start?