both bikeworks and bicycle habitat will be very familiar with the fixed crowd. skip chelsea bicycles; their service leaves much to be desired.

larry and jeff's bicycles (2 stores, upper east side) is a great shop, but i've only ever dealt with them for my road bike...

enjoy NYC - it's great on 2 wheels!