You need the permissions password. You have the password for opening the document, which is not sufficient for removing security. When you set up password security, you have the option of setting a document open password, but it's not required to set up security restrictions.
I'm using Pro XI on a Windows 7 Enterprise system and I'm having a similar issue. I didn't set a document password, only a permissions password. The password works fine on the template with empty fields but when I try to edit an already completed form (I am the form author) and it asks for the permissions password, I get the same message about the password being incorrect and to check the Caps Lock (it's not on).
This is a different question than the one that ahaywiy asked. You'll be better off asking your question separately. While doing it keep in mind that if you set only the Permissions password then you can open PDF without entering any password. What do you mean by "The password works fine on the template with empty fields"? What are you trying to do: to change permissions? What do you mean by "try to edit an already completed form"? You want to fill some form fields and Acrobat asks you for the Permissions password at this point? Or do you want to change permissions on a completed form? Have you saved and reopened the completed form?
Include answers to these questions when you post your separate question.