So if you want my advice, check out his iTunes Celebrity Playlist and look for the distinctive acts with distinctive sounds that he hasn't style-parodied YET. Here's a list of potentials:
Alice Cooper
The Ramones
I think an Alice or Ramones style parody would be awesome...(not that I've been wanting an Alice style parody FOREVER!!! )