Le mieux est de passer par l'utilitaire de disque d'OS X pour formater ton disque.
Ensuite, ça se passe dans les préférences de Time Machine pour choisir la destination.
Pour formater ton DD, soit tu démarres sur le CD d'installation d'OS X si tu es sous Snow Leopard (c'est la procédure que tu décris), soit tu passes par la partition de restauration si tu es sous Lion/ML.
Après c'est dans l'utilitaire de disque, tu sélectionnes ton disque dur interne, et tu choisis effacer, ou formater.