(Scroll down for the actual fix)
So things were even more complicated than it seemed at first.
In order to maintain compatibility with MS-Windows, Apple uses a hybrid UEFI and Legacy MBR mode. Apparently, there is an NVRAM value that tells the firmware whether to attempt to boot in UEFI mode (OS-X) or in legacy MBR mode (Windows). That value is controlled by your selection in "System Preferences > Startup Disk". (Don't ask me why, ask Apple)
Now in order to boot Ubuntu from my external HDD, I first booted from a DVD that I had burned an ISO of rEFInd to. (Selecting "EFI boot" with the DVD icon when holding the Option key during startup). After booting from that DVD, I then selected my external HDD to boot from inside of rEFInd.
This is where things start to go really strange. After telling rEFInd to boot from the external HDD, the purple GRUB screen never came up (Yes, I had set a delay) and furthermore, there was no purple dot boot animation. Instead, it was the scrolling white text boot up.
From what I can tell looking at rEFInd more closely before hitting boot is that the Ubuntu option was actually to load a specific kernel, and not just boot from the disk.
What that means is because rEFInd is, well, EFI obviously, and it functions essentially as a GRUB replacement, that even though Ubuntu was installed in MBR mode to the external HDD, it ended up being booted in UEFI mode.
That fact is very important, and you'll see why in just a second.
So then I let the Software Updater run some updates. Looking at logs, it seems that the
update-grub command was run during the install process. This is where all the bad things happen. Now at this point I don't know exactly what happened, but here's my best guess: The grub updater got confused since grub was installed in MBR mode, but Ubuntu was currently booted in UEFI mode. Because of the confusion, and the fact that the boot loader is installed to a different place depending on which mod you are booted in, the grub updater makes a big mistake and installs grub in MBR mode to the internal HDD.
Now for the actual fix!
In my particular case, the OS-X partition was still bootable if I held the Option key during startup and selected the "Macintosh HD".
After booting OS-X you'll want to open System Preferences, and then go to Startup Disk. Select the OS-X volume, hit apply or whatever, reboot, and BOOM! the Apple logo shows!
Now, just FYI, I think that although that fixes the problem, GRUB still resides in sector 0, but I don't think it'll do any harm there, and certainly not if you install Windows in Boot camp, since Windows' boot loader would just overwrite it then