That's strange, especially since I've installed Ubuntu 12.04 in that same configuration (sda1 = root, sda2 = swap, primaries not limited) a few different times in the past couple days. It booted and worked OK, and I didn't get any error message. And it sounds like you did it right....
Referring to this KB article: http://www.terabyteunlimited.com/kb/article.php?id=279
As long as you do steps 3 through 6, that will ensure that the Ubuntu installer will see the correct partitions. It is especially important to do step 5, so that the MBR gets loaded with the partitions you want, before booting from the install CD. Also, even though you get that error, have you tried actually booting Ubuntu after the install to see what happens? Also, make sure the root partition is large enough.
Other than that, if you can post your partition table as seen from the Ubuntu installer, and post it here, that could bring something to light. To do that, you can choose the "Try Ubuntu" option, boot up to the Live CD desktop, and then run 'sudo fdisk -l' from a terminal.
Edit: Also, which file system did you select for the root partition?