I too had been successfully using the cellphone SMS security key to my Rogers cellphone, and recently had it stop working.
I spoke with Rogers technical support today (March 23 2012) about SMS security key messages not being received from Paypal. They checked my cellphone account and it has NO blocks or filtering on it. While I was on the phone with them we successfully exchanged SMS text messages, including a message containing only 6 digits as a message body.
I also generated an SMS security key message from Paypal while I was on the phone with Rogers. It was not received on my phone, but they checked and could tell that no text message was processed by their system directed at my phone number. (They say they can see all text messages, and if there was ANY filtering anywhere within their system they would see the message being rejected.)
They suspect that some recent change - perhaps within Paypal or one of its subsystems - has changed the way cellphones are associated / accessed. I wasn't able to test, but perhaps the "1" is no longer needed in front of the area code and number - I had entered my number on my profile as 1aaannnnnnn, where in Canada 1 is the long distance / country code indicator. As I say, until recently this was working.
I've sent a message with the details to Paypal tech support, and I'll update the community when I get a reply from them. If anyone else has already discovered the solution, please let me know!
