Sounds like you just need a wildcard CNAME record like
*.domain.com. CNAME www.domain.com.
Otherwise, you don't need to have your DNS at this host if they can't figure it out.
Tell them you're contacting other hosts and the one that sets your DNS up correctly is the one they'll lose your business to.
