I would have tried classified ads in a local (Brooklyn that is) newspaper. If you are smart about it, you never know what some people would pay for the name.

I recommend advertising the potential start of a company called "Brooklyn Records", not the actual domain. Just make it sound like you can start a great company with a great name at [THIS] price. Or, if you don't want to post the price, tell people to contact you for pricing.