> At this point in time all Linode should know is 
  > SHA-2(password) and they can't use that to derive
  > bcrypt(password).
  > ...
  > In order to do this without people logging in Linode would have
  > to bcrypt hash the SHA-2 hashed passwords and then keep doing
  > that for all password validations.

They just could make the intermediate step bcrypt(SHA-2(password)) via some lockstep code/db backend update. Then on next user login after verifying against bcrypt(SHA-2(password)), update the db to the more straightforward bcrypt(password). At the very least this would increase the difficulty of brute forcing in the meantime.