It does sound like the public-key crypto is one of the best ideas for internet-enabled 2-factor so far, though I haven't quite wrapped my head around the implications of the weird "hash it one less time" backup code method. Based on the description on the skey page here[1], here's some pseudocode of how the challenge works without your phone:

  # Create password
  client ->  hashit 64-bits-of-random-data 10000 > backup.crypt
             hashit 64-bits-of-random-data 9999 > backup.code
             tell-user "Write this down!" + backup.code
             remote-copy user@server backup.crypt
  server ->  store backup.crypt
             counter = 9999
  
  # Log into the server
  client ->  request-challenge-from user@server
  server ->  send-reply "send me hash 9999"
  client ->  read-value "Tell me the backup code you wrote down" backup.code
             try-login user@server backup.code
  server ->  hashit backup.code 1 > trypw.crypt
             if trypw.crypt != backup.crypt
                 fail "Error! wrong backup code"
             else
                 success "Code good!"
                 counter = 9998
             done
  client ->  hashit the-same-old-64-bits-of-random-data 9998 > backup.code
             tell-user "Write down the new backup code!" + backup.code

Edit: so every time you attempt to use a backup code, if it works, you write down a new backup code. Depending on how they implement this, there's a couple fun attacks based on things like the randomness of the pad, if we can force it to reduce the rounds used over a pad (which might not even matter if it's something fast like SHA1), etc. The [remote] security of the second factor now depends on whether or not you can guess a 60-bit "random" hash. Fun stuff.

If I were them, i'd just do e-mailed password resets and leave it up to the user to secure their e-mail. This complicated scheme is way more likely to be exploited somewhere in implementation, considering how rare and custom it is.

[1] http://www.ece.northwestern.edu/CSEL/skey/skey_eecs.html