I had the same problem...here's what I learned.
In the manual the first step requires you to do what you have been doing so that the in car homelink detects the type opener you have...most likely one with a rolling code. Once the in car system learns that from your hand held remote opener, you will then go the opener itself , press the "training" button on it, return to the car and press and hold the in car opener button twice for 2 seconds each time. Afte that, the button should open your door. It's kind of a two step process and the owners manual doesn't really clarify that.
One other item to note, my unit is a genie and manufaturer let me know that it will work with up to 7 remotes. So if you have multiple cars with built in openers and a bunch of hand helds laying around, you could have probelms with a transmitter not working when you add / program a new one. I have 4 cars with builf in openers and as many remotes, so I had some issues. Too lengthy to explain in this post.
Post again if this does or doesn't work for you. I may not be explaining very clearly.