Getting into new music is a process of a) getting outside of your current comfort zone, as Fire_Starter already noted, and b) having faith in exploration to get you there. Being kind of old-fashioned (and on a crap connection when not at work), I can't speak for lastfm's efficacy, but here are some other thing you might try while trawling said service.
- trawl through the What Are You Listening To Right Now
thread and look up bands that the description sounds interesting from. Not just for their music; if you like the music, look them up on Wikipedia and see who the current members have played with in the past, what past members are doing right now, etc. If you Google them and find people on music forums slagging them as a lame ripoff of band Y, dig up band Y's stuff and listen to that and do the same process. If people are promoting band Z as "the new band X", go ahead and listen to them as well.
- this is much less useful than it used to be in the pre-digital age, but if you're noticing that a lot of the bands you like tend to be on the same couple indie labels, anything that you find recorded on that label is worthy of consideration. When I was in college, people used to buy anything recorded on Matador because the Frogs were on Matador and that gave it immediate credence; I have yet to find a bad record recorded on Deepsend (though they did refuse to sign Porphyria because they wore bandanas), even though the kind of death metal that they specialize in can turn pretty bad pretty easily. Majors, of course, are too big for this to be useful.
- deliberately listen to music you don't want to bother with. If you go to see a band you like live, go at doors and see the openers, then stick for the headliner if the band you like is opening. You'll never get into a new band if you decide they suck and don't go see them. If you're at a big show and someone hands you a flier for a DIY gig, don't just throw it away; look up the bands playing and go if you're interested and don't have any other commitments. If you're going to a festival anyway, go all the way through the fine print at the bottom of the bill and see all of the undercard bands that look interesting at all, or at least as many as you can.
- read through Last Plane To Jakarta
, including and especially the archives. John Darnielle has interest in a ridiculously wide range of music and a penchant for digging out gems from the bottom of any pile he comes across, and the writing is pretty good as well.