are you camping, or backpacking? you make it sound like you checked the park web site for availability. but when i looked, the car campgrounds are just first come first served, and are stated to not start filling up until late March,
http://www.nps.gov/cany/planyourvisit/eatingsleeping.htm and Island In The Sky's backcountry permits remain nearly 100% available for the entire month of March.
http://www.nps.gov/cany/planyourvisit/backcountrypermits.htm
also, if you were interested in the Needles district, you can self issue a backcountry permit there up until March 4.