Having just fought and won this battle, I'd like to add a step / precondition:
I have a Genie garage door opener with the Homelink / rolling code, and it wouldn't program with my new Lexus. I followed the instructions serially 10 times, followed the instructions on this forum and others, no luck.
Reading the Genie FAQ's, I found my problem: the Genie will only hold the codes for 7 transmitters. As I've had several cars in and out of the garage, the opener memory was full. Erasing its memory (push and hold the learn button for several seconds on the opener), then repeating the programming was the trick.
So, count your cars and openers, old and new, and wipe the opener memory if you're having problems with a total near 7.