Before reading: The answer below is meant for Ubuntu users who have just updated/recovered/reinstalled/installed OSX. It's likely that the answer will work if this isn't the case (for example, if there are any inconsistencies in your partition table), but I'm not sure.
For me, this happened after updating to OSX Mavericks. Basically what may have happened is that OSX created a recovery partition ("Recovery HD") that the system only detects sometimes. For example, GParted in Ubuntu will see the recovery partition fine, but when listing the partitions in terminal (
fdisk -l), you may not see the partitions.
Diagnosing the issue: Did the OSX update/format/recovery cause this problem?
In order to diagnose that this is indeed the case, first use grub rescue to boot into Ubuntu. In order to do this, follow this page or see if any of the other answers on this question can get you into Ubuntu. For me, running the below commands temporarily allowed me to boot the correct partition. Depending on how your hard drives and partitions are set up, it may vary:
grub rescue> set prefix=(hd0,6)/boot/grub
grub rescue> insmod normal
grub rescue> normal
Now, login to Ubuntu and check GParted. If you see the recovery partition, open up a terminal and type
fdisk -l to see if that detects the recovery partition. If it doesn't list the same partitions, check the device/partition column and see if those also don't match up (e.g., in GParted your boot partition may be
/dev/sda4 but is
/dev/sda3 when running
fdisk). If this is the case, keep reading. If it's not, it looks your partitions are lined up correctly. You can either choose to keep reading and follow the instructions (which, if grub was working before the restore/reinstall/etc..., this should work properly), or just reinstall grub on the right partition.
Fixing it by removing/merging the recovery partition
To fix this issue, what we want to do is get rid of the recovery partition - it's causing issues and inconsistencies, and removing it shouldn't cause damage. Ideally you want to merge it with the normal HFS+ OSX partition, so follow this question and answer here. After merging, grub should be back to normal.