Found out about Discover Music - Pandora through Lifehacker (new must read blog I just discovered). I'm not sure exactly how it works, but basically you tell it a song or artist you like and it finds and then plays a song by that artist. You give a thumbs up or down as to if this is the type of music you like, and if plays music similar to that.
In my case I started with typing in "Blue Rodeo" as the band, it played "Bad Timing" as the example tune, and then from there played "I'm Over You" by Keith Whitley. Not exactly the same genre, but the same "sound". From there it went to "You Woke Up My Neighborhood" by Billy Bragg, who I've never heard of, but again, had the same sound.
I'm not sure if they use a similar system to audioscrobber for their data or what (it says it's part of the Music Genome Project). Seems to work well though.