ok, I'll give this a shot.

First head over to the SE account management page and log in.
At the near bottom left, you should see a window that says Services and Options. Click the "Select Service" link and then the FFXI link that appears next. This should take you to the screen that shows the POL accounts that are registered to your SE account. Get a pen and paper handy and take note of the POL ID that matches your character. Note that the ID should be 8 characters, 4 capital letters and 4 numbers. When finished click the options list button.

The next screen should show your characters along with the expansions you've registered ect. At the bottom you will see several options with the top being update playonline password. Click update and change your password to whatever you see fit and write it down near your note for the POL ID.

Now that you've done everything once again, with frustration I'm sure, exit out of your browser and launch your game.
On the first screen click on your login of choice and choose the delete option. If you only had one character your screen should now be blank. Pick the Add member option on the left and enter the required information, taking note of the capital letters for your POL ID. Your screen should look something like this:

Member Name - This can be anything you choose. Personally I pick my main characters name.
Playonline ID - Your pol id, take note again of the 4 capital letters and 4 numbers
Set password - 2 options, Not set and save. For me it is easier to use the save option. Otherwise you will be required to enter 2 passwords each time you log in.

Playonline Password - This option will highlight if you choose the save option from above. Carefully enter it in if you picked to do so.

Member Password - This is for extra security and is not required. It will prompt you to enter yet another password before logging in. Personally I do not use this.

Confirm Password - If you opt for using the member password this will highlight and you will need to enter it again to verify.

Square Enix ID - Your SE id that you use to log in to your account page.
One-Time Password - Again, 2 options Do Not Use and Use. If you have bought and registered a security token from SE and use it to log in to your management page online pick the Use option. Otherwise keep it at Do Not Use.

Once finished click the register button at the bottom and try logging into the game again.

Sorry for the long winded post, but I have had this happen more then once, especially when I change my POL password from the site. For some reason the log in for the game doesn't always like info changing once its saved and deleting and reentering everything has worked for me every time.

Good luck and hope that helps =)