If your really serious about being challenged, check out LFS(Linux From Scratch)
Gentoo also is a good choice, but not as complicated as LFS(whether thats good or bad)
Gentoo does have great support though, check out their forums:
I think slackware is a good choice for the intermediate linux user, although it is heavily dependent on the command line.
As to your question, what software did you use? You don't need to use any third party software to change anything in grub. All you have to do is edit /etc/grub.conf with your favorite editor. To change this now in your situation you will have to use some sort of a boot disk to get into your linux partition. For instance you could use a live CD, most likely though, it sounds to me like you have over-written your grub in which case you will have to re-install grub. To see how to install grub, see here for a manpage:
Although if your going to install a new distro of linux as you say you are, you shouldn't be to worried about this as you can just install lilo or grub during the installation of the new distro.