I've found Rdio to be the best service for this, especially for new music discovery.
I'm a bit worried now that they're switching from Echo Nest though
Do you know Pandora? If you can't access the site, you could use a browser extension called "MediaHint". There's also http://rd.io/.
And spotify, etc, etc, etc
I'm not sure that pandora is available in the UK ?
I tried it when it started and wasn't so keen on the recommendations... might try rd.io
Just use Spotify, choose an artist you like and generate a radio station from them. Then it'll play you new related artists, and the original one you chose.