When you set the password for the .PST file, did you close Outlook and re-open it before attempting to open the .PST and test the password? Outlook seems to save a .PST file password for the session that it is open, even if you close and re-open the file itself. If you close Outlook, then it will prompt for the password the next time you try to access that file.

Basically it goes like this:
Open Outlook. Open PST file (or access the PST file in the Navigation pane if it is already open). Enter password for PST file. Now as long as Outlook is open, every time you access that PST (even if you close and open it), you will not have to re-enter the password. Once you close Outlook, then the next time you try to access the PST file it will prompt for the password.

If you are not being prompted for the password after closing and re-opening Outlook, then there's definitely something wrong with the program on your system.

Hope this helps.

-SW