One quick thing: any plans to change the default user name that's assigned after FB login?
Those guys behind the counter started kinda like that as did any DJ worth his/her salt, and honestly I don't think there's a better way of music discovery. Having something physically there, staring at you reminding you that you forked out cash for it, something you come back to again and again forms an authentic experience that can only be replicated in part by digital.
Check out stores like Hardwax, Space Hall, Kristina records, Naminohana, honest jons or whatever is local to you. Look up the event listings in Resident Advisor and grep the artist names. Actually leave the house. :)
Also, have you actually gone into record stores and previewed records before buying them? I may purchase this record player[1] as a way to check out records at the store, but I wasn't sure if this was a thing store owners typically allow. Any insight?
[1] http://www.amazon.com/Vestax-VES-HANDYTRAXUSBBLK-Handy-Trax-...
try this: http://record-shops.org/
EDIT: And I believe you can view playlists from archived contests if you register, so you can focus the discovery down more to your liking.
Look for artists from the same label as artists you like, look for labels owned by the artists you like, look for artists that have appeared alongside them on compilations, look for compilations/mixes playlisted by them, look for other artists they've collaborated with in the past, look for reviews of records you like and see what other music they compare it to, look up old shows theyve done and see who else performed, look at other shows organized by the promoters of those shows, etc etc etc.
Never be afraid to listen to something just because you like the name or the cover. Also, it pays to check out any record that has the word "afro" in the title and/or a photo of the band standing in front of a spaceship. You can develop your own heuristics :)
http://discogs.com and http://allmusic.com are useful in this regard, as well as good old wikipedia, and reading the notes on the records themselves. And the great thing about spotify et al is that all this can be done in seconds, rather than years.
The big secret to knowing about good music: listening to a lot of shit music until you hit paydirt.
Not sure why you feel like you "suck" at music discovery. First of all, it's not exactly a skill...so you can't really suck at it. In other words, there's no "wrong" way to discover new music except not doing it at all. Second of all, the means of discovering music you described is the primary way that 96% of the world discovers new music. Few people hear an artist, then immediately look up their label and listen to a few other things the artist has done, as well as other songs from the label they're on. Most of the spread of music occurs via word-of-mouth, or people listening to whatever their friends are listening to.
Honestly there isn't anything better right now than getting music from your friends, or just going out all the time and hearing new tracks from DJs/bands/whatever.
It could also be a sibling thing, as 2 of my younger brothers are very much on the cutting edge of new acts (following tiny blogs, watching new soundcloud accounts, etc.), and I feel like I end up mostly relying on hearing new things through them. There's even a clear delineation in my musical tastes in the early 2000s when my siblings began finding music and I shifted away from relying on my parents' stuff to theirs. It's just something I think about when I'm strolling through spotify playlists most days.
And in regards to the FB name, there should be a way. If you go under settings (gear icon) in the upper right, it should lead to a drop down where you can go to your settings and change your username. Let me know if this doesn't work for some reason.