The Protomen are absolutely amazing. I've never been a particular fan of Mega Man, but their music video (see link) really hooked me and I bought both their albums. If you aren't into NES-style chiptunes (I love them) you should stick with the first album, though.
The Protomen are basically a band that creates rock operas surrounding the story of Mega Man. Their title track, Hope Rides Alone (the music video linked to above) is pretty amazing, but a lot of their other tracks are just as good, if not better. The Will of One is just incredible, as are The Stand and Sons of Fate.
As with most rock operas (another personal favorite: Beethoven's Last Night), I found I had to listen to the Protomen album multiple times before I caught everything that was going on. The first few listen-throughs I simply found the material compelling, and a good listen. After I really understood the story, however, I discovered a truly unexpected emotinal weight to it. I've always thought of Mega Man as largely uninteresting, lightweight robot fare (apologies to fans), but the story presented here is something I won't stop thinking about for a long time. This just became one of my favorite albums.