Eu costumava usar o Bluehost e passei por esse cenário exato com eles. Eles permitem algum controle de DNS pelo usuário, mas para fazer o que é necessário para o Google Apps, você precisará ligar para eles e solicitar que as alterações sejam feitas. Eles fizeram isso um milhão de vezes, então tudo que você precisa fazer é dizer a eles que está configurando um domínio do Google Apps e eles provavelmente saberão exatamente o que você quer que tenha feito.
Acho que levou apenas algumas horas após o telefonema antes que as alterações fossem feitas e, em seguida, mais algumas horas para essas alterações se propagarem.