PayPal and eBay shared the same keyfobs for a long time, but sometime about two years ago, PayPal logins stopped working for me and nobody from their side could figure out why. Long story short, the only fix was to turn off the keyfob and use PIN codes sent by SMS.
I am not sure if this really impacts security as PayPal was trivially easy to social engineer and have the keyfob taken off a target account, so having a keyfob on your account really didn't mean that much.
Now eBay is doing the same thing. Oh well.
Interesting - my fob never stopped working. I changed over to using the android app instead of the physical fob (because my old fob looked like it had been through the wash too many times), but I've never had a problem with it.
My guess is that Paypal/Ebay don't actually know enough to debug subtle problems with the system, so you got screwed.
Annoying, and now we all get to be annoyed.
Note that so far my sign-in still works with the app - they haven't actually started forcing people off of the fob yet.