Most of the previous respondents are correct when they say that you can usually do what you need with a GPT partition table layout, but since there are valid reasons for wanting to use MBR, I think I will just answer your question instead of assuming you are wrong for asking.
To get rid of the GPT, you need to remember that with this format, there is a partition table written to the end of the drive, where it will remain if you just try to delete it with fdisk or a non-GPT aware file system tool. What you did with parted did not address this partition table.
To erase GPT, you need to use something like gdisk. Enter
gdisk as root at the prompt, and then tell gdisk what device you want to look at (i.e. /dev/sd??). Use gdisk to write a protective MBR to the disk just to make sure you have access to some MBR data structure. Then you can navigate to the expert options section (press
? at the different program prompts to see the options available to you at different times) and find the option that says "Zap (destroy) the GPT data structures and exit." The program will prompt for confirmation, then ask you if you want to preserve the MBR structure. Do preserve this.
After that, it should be as simple as rebooting your computer (because the kernel will still be using the old partition table and it needs a restart to update), and then firing up fdisk and deleting the remnant of the GPT partition. You will still see the same warning about using GNU Parted that you saw before, but you can ignore it this time, as it will go away when you delete the partition.
This will give you an MBR partition table system on a blank drive onto which you can reinstall an OS. If you are attempting to do this with existing partitions, it is quite a bit more complicated and in some cases not even possible, so I would recommend that you simply back up your data and do it this way.