For the Hammerstein shows in October '07 I stayed here:
http://www.chelseahostel.com/
I booked a private room and really enjoyed my stay there.
I never stayed at hostels before (well I did when I was a teenager, aaaages ago
) but this was really good for a hostel. Very basic room of course but in a nice area, walking distance to for instance Madison Square Garden, close to many restaurants, subway etc. I normally stay in hotels too, but even more expensive hotels in NYC had worse reviews than the Chelsea Hostel.