Chances are your disk originally contained a GUID Partition Table (GPT), but you created a new Master Boot Record (MBR) partition table over that with a tool that doesn't understand GPT. Because GPT takes up more space than MBR, this means that there's leftover GPT data, and parted is becoming confused because of that.

If this analysis is correct, then the easiest solution is to run FixParts on the disk. FixParts will offer to remove the leftover GPT data, and thereafter you should be able to use the disk normally. (You don't need to do anything else in FixParts; just tell it to remove the GPT data when it asks you about this and then exit.)

There is a caveat, though: It's also possible that you had a GPT disk but that something accidentally wrote an MBR partition table to the disk. In this case, you probably want to recover the GPT, not wipe it out! If this is the case, the solution is to run gdisk on the disk. It will detect the problem and ask if you want to use the GPT or MBR data. Tell it to use the GPT data, check that it's correct by typing p and comparing the output to whatever you believe to be correct, and then type w to save the changes.

Both FixParts (fixparts) and gdisk are part of the gdisk package in Ubuntu. It's usually not installed by default, so you may have to install it by typing sudo apt-get install gdisk.