Your garage door opener (the unit mounted to the ceiling) may have a "program learning button" on it as well. Newer models (less than 10 years old) use a scrambled type code each time the button on the remote garage door opener is used. (Before this you could drive around with your remote opener and possible open up somebody else's garage door.)
The procedure for my garage door opener unit was to push a special button (in my case it was red.) The unit then sends out (for about 60 seconds) the programming needed by your opener in the D to learn the scrambled code that's required. After pushing this special button then you follow the procedure in your D manual to program the button.
Hope this helps?