At The Echo Nest, we just rolled out the beta version of a new API method: artist/suggest - that lets you build autocomplete interfaces for artists.