Yeah, thats typical. You will have better luck in large wine stores like Total Wine, or in eclectic little wine shops. Some of the most interesting meads I've found are often in stores...
For ethnic meads, hit the neighborhood shops that serve that ethnic group. I found some really *excellent* tej in Little Ethiopia in Washington, D.C. I expect the Ethiopian areas in NYC are the same. Likewise hit the Irish and Polish areas, you'll likely find some from that area being sold in their local stores. The best tej I ever had was sold to me by this guy who was sitting on the stoop of a building housing an Ethiopian shop. The owner recommended him. The mead came in an unmarked bottle wrapped in a paper bag.....
Near NYC, about an hour from the city is Brotherhood Wines, which has a decent mead:
http://www.brotherhoodwinery.net/pages/
Also in NY:
Long Island Meadery
1347 Lincoln Av Suite 11
Holbrook, NY 11741
http://www.limeadery.com
Tell Paul Holm, the owner, that you're a Gotmeader. Paul has a large variety of meads, in all sorts of flavors, ranging from very dry to sweet. Try the root beer mead if you're feeling adventurous, its neat!!
Earle Estates Meadery
Rt 1, Box 246, Tucker Hill Rd
Locke, NY 13092
http://www.meadery.com/
In New Jersey:
Saba Tej (Organic Honey Wine) Co.
15 Park Avenue
Rutherford, NJ 07070
Araya Selassie
phone: 888-772-2283 (tell him Vicky Rowe sent you, he may remember me)