Tell them to restart apache with SSL. They most likely did an an "apachectl start" instead of "service httpd start" or "/etc/init.d/httpd start" these will include all the directives to get SSL working.
Have a look on these forums... a lot of good DA hosts post here.
When I was still a reseller, I was considering SimpliHosting at one point (not sure of their URL, you could Google for it) - they seem to have good uptime and good pricing.
I run a web host myself, but I also use Liquenox.net (they post as Sumaleth and l0rdphi1 on these forums) as a backup host for my hosting site. They use DA and their service has been excellent. I'm not sure if they accept adult content... just ask them. Highly recommended.