Does the problem occur also on parallel logins, i.e. if you try to mount sshfs while having an open ssh session? If not, then I would guess that you have your home directory encrypted? In this case $HOME/.ssh/authorized_keys$HOME/.ssh/authorized_keys would only become usable on the removeremote machine after your first login (using your password).
Check out https://help.ubuntu.com/community/SSH/OpenSSH/Keys#Troubleshooting for an explanation and the required workaround.