Apple - How to fix "Error: -5341: MediaKit reports partition (map) too small" after upgrading to a larger hard disk?
Your partition table does not know about the larger hard drive yet. While Disk Utility also queries the hard disk size and lets you request it to enlarge your partition, it will fail when finally changing the partition size (after doing a file system check).
This can be solved on different ways:
One is to destroy the GPT (partition table) and recreate it manually, which is a rather annoying and error-prone way of fixing the problem as it's easy to mess up when adding your partitions again.
An easier, better way is to run gparted, which is also included in current Ubuntu Desktop Live images (or is easy to install from their packages repositories) and probably lots of other Linux disks. After starting it, it will recognize the wrong disk size in your partition table and ask whether it should fix it for you. After fixing the table, reboot to OS X and finally enlarge the Volume.