I could be wrong, but I'm pretty sure it can't be done. Sub domains work off of DNS, so if there is no DNS entry for profile.site.com, the DNS lookup will fail and the browsers request will never make it to the server for the rewrite to happen.
Naw. These guys got a cheapie hosting package that's pretty limited. They don't even have SSH access, so I'm just going to have to tell them it can't be done. Thanks.