If it's your first time setting up sync on your mobile then likely you are missing a required step.

See:

How do I add a device to Firefox Sync?

What step could that possibly be? I tried to setup sync both ways, via pairing and then recovery key, with the same result. Other desktop devices have no problems.

Cbaldwin, do you have more than one version of Firefox on your mobile device?

Twalker, had a previous version running sync. Upgraded today after receiving notice that a new one was availablethe and then afterward started having problems. For the record, my password was changed about a week ago and am not sure if I changed it in the older version of FF mobile before upgrade. I wouldn't think it would matter since it didn't remember that this device was paired previously after the upgrade anyway...

Cbaldwin, ok. Something in Android doesn't allow Firefox to support two versions of it with Sync. You'll need to remove the Sync account on the old version of Firefox remove that old version of Firefox, then setup Sync on the new version.

You would think it wouldn't matter regarding changing the password in old version but sync is picky, plus even though you updated it's still thinks its linked to the older version, this it won't work properly on the new version. You're better off removing it completely from your mobile & removing it & data associated from Desktop portion is applicable. Then add on your mobile again & treat as if it were new first time sync.

Twalker, Thanks for your assistance with this.

Well, I tried a number of things including reverting FF back to previous version, disconnecting sync, wiping data(using Ti Backup), and then reinstalling FF from Market. No dice...So, I tried to identify the app that is causing the persistent password requests and found it to be "Sync Service". Reverted that back to the last version before upgrade and repeated steps above. FAIL.

In all cases, sync still knew I had a sync account before I even setup the new one in the upgrade! Even though a complete wipe of all FF data using Ti Backup!

So now what?

As I mentioned previously, you'll need to go into sync & remove it from each client where it's installed on as it's still going to associate old version if it's left on a sync on your desktop for example. Removing from just one local client such as mobile or making any changes to one specific version is pointless.

dude... It happened to me as well... I put my sync up from a laptop that i was using... I formatted it and then installed another os and tried to access my data. And it just wouldnt. It just kept saying again and again that the password was wrong. But at the same time, I was able to log into mozilla. org. Some people said that maybe the server was down and it would get back up later. At the end, what worked for me was the simplest of things... i dont know if you are already doing this, maybe it had not made sense only to me.. but still it was the simple act of putting your email address where it says "Account."