Even if the laptop was stolen, how would someone change the passwords? Don't they require you to login first before you can change any password?
Anyway, I guess it the thief went this far they may have changed the recovery secret questions as well.
With Yahoo!, you could get in touch with customer support and they can assist recover the account. With Gmail, I am not sure.