Occasionally the A-Records associated with a sub-domain remain, even after the sub-domain has been removed from the system. This prevents you from re-adding the sub-domain to the system, as you have discovered.
Recently, I waited over a week for the A-Records to be deleted for a sub-domain I removed (and wanted to re-add). I ended up lodging a support request and support ran a manual DNS update on my domain, which removed the A-Records.
Save [color=#CC0000]$50[/color] on DreamHost plans using [color=#CC0000]PRICESLASH[/color] promo code (Click for DreamHost promo code details)