In it's efforts to fight piracy and the jailbreaking gear that has come out lately, Sony has updated the PS3 to 3.56 firmware. The update has a glitch, it makes hard drive upgrades impossible on most PS3 models.

The problem seems to stem from Sony's latest update which was rushed, an explanation from a post on NeoGaf below:

The 3.56 patch is a tiny patch which simply add/changes files in the 3.55 software. This differs from most patches which download the entire firmware. Since part of the software on models with 16MB of flash memory is stored on the hard drive, those PS3's need to reinstall the software when upgrading the drive. PS3's with 256MB of flash memory store all the software in the flash memory so it isn't lost on a drive upgrade.

Anyway since 3.56 is a hot patch and requires 3.55 to be installed prior to updating, you can't install 3.56 on a new drive. You also could install 3.55 when upgrading if not for Sony's software version checks.

Sony will most likely patch the latest firmware and remove the current bug, it's just a matter of time.