I actually tried to address the hostel situation under Hi Hostel. I think they have a website as well. Unfortunately, I cannot comment on whether they have any in NY, I'm assuming they must. I know that they have it in Chicago - but you should save that trip for another time.
Motel 6 and such is a good suggestion but honestly, sometimes those prices are just as much as some of the others. Look on the accomodation on this site. You may have better luck.
Have a great trip.