Update:
I noticed that I got errors when verifying the disk from the recovery Disk Utility if the partition was AF05. It only verifies successfully if the partition code is AF00, so that seems to be the correct partition code. Unfortunately, I used the Repair Disk button from Disk Utility and it hosed my 2nd partition so that it would no longer would boot even in to the Recovery HD. I had to go back into my Lubuntu and use gdisk to fix the 2nd partition (again) in order to get it to boot into the Recovery HD once again.
At this point, my plan is to try to install OS X onto a USB drive, using the Reinstall Mac OS X option from the recovery partition. That would give me a lot more flexibility to install it back onto the original HDD, etc. What do you think? Is this possible?
Oh...In order to try to get it to boot normally I also tried putting 128 MB of space between partition 2 and partition 3 per this Technical Note from Apple: https://developer.apple.com/library/mac/technotes/tn2166/_index.html
This involved the following math:
128 mb converted to bytes = 134217728 bytes ...divided by the sector size of 4096 (found using lsblk) = 32768 sectors back that I needed to move the end of the 2nd partition. The existing end sector size was 975503591 so you subtract 32768 from that and the new end sector size of partition 2 becomes 975470823.
However, this didn't make any difference at all. LOL. Not sure why most of the google results I see have the 2nd and 3rd partitions directly adjacent but Apple's Technical Note says otherwise, lol.
----------
Well, I put a 16 GB USB drive in and told the Mac installer to install to it. At that point, it prompted for an Apple login. I entered mine and it says:
"This Apple ID has not purchased "OS X Lion"
Grrrr....
Doesn't this defeat the whole purpose of having a recovery partition? If I have a recovery partition then I must be legit, right? So frustrating that it requires me to prove that I bought Lion when I have a piece of Mac hardware in front of me. The purchase of Lion was when the computer was purchased by the original user!!
Is there any (legal) way around this??