Well after hunting the internet without luck for about a week, I finally decided to do things the old fashioned way... through trial and error.
I eventually worked out this:
When you edit the /etc/pam.d/system-auth file and modify the following line, you'll break the users ability to modify their own passwords...
password sufficient /lib/security/pam_unix.so nullok use_authtok md5 shadow remember=5
Once I removed the "remember =5" part from the end of the line, users were able to set their own passwords again.
This of course means that users are able to set their passwords to the ones they used previously (which blows... ), but it appears to be the *only* way I can make this work.
I just thought I'd post this up to hopefully save some time for some other poor smoe
If anyone has any ideas how I can get password history working "correctly" I'd love to hear it.
After some further research, I finally have the answer to this issue. I found that you have to manually create the /etc/security/opasswd file to store the old passwords.
If you fail to create the file when enabling password history, the feature breaks.
I've created the file now and everything works fine.
Hope this helps.