ok, while I've never personally experienced this error it looks pretty clear.
I think what you need to do is take another full backup of the primary if you can. Then in order
to get mirroring going you have to take an initial log backup as well... so what I do is I take my full backup, then right away I take a log backup and restore them both on the other side.
That should get you going.
And what recovery mode is your DB in... you should be in full.