Pairing with a HRM Pro Plus

I have an Edge 800 that won't pair with my Garmin HRM-Pro Plus.  The Garmin website says that the HRM-Pro Plus is compatible with the Edge 800.  The directions say,

1.  Put on the HR Monitor  

2.  Turn on the EDGE

3.  Bring the Edge to within 3m of the HR monitor

4.  Select >MENU>BIKE SETTINGS>HEART RATE>ANT + HEART RATE

5.  HEART RATE MONITOR>YES

At this point the EDGE gives me the option to SEARCH, but when I click on that it takes me back to step 5.  

6.  Press what I assume is the on/off button, but when I do that, the EDGE turns off.

At no point do I get a message that says my EDGE is paired with the HRM Pro Plus and at no point do I get a message to rescan.

Any help would be greatly appreciated.  BTW, I have paired the EDGE with an old HRM, but I have a new one now which I would like to pair.

Regards,

WBO