[CentOS] passwd problem with new vps

greetings,

I am setting up Centos 6 i686 remotely, on a new VPS.

A problem I have is that I cannot set password for new users. I have
created one with

useradd -m new_user

but when I type 

passwd new_user

this is the result:

[root at vps ~]# passwd new_user
Changing password for user new_user
New password: 
Retype new password: 
passwd: Authentication token manipulation error
[root at vps ~]# tail /var/log/secure

Sep 27 17:30:30 vps passwd: pam_cracklib(passwd:chauthtok): pam_get_authtok_verify returned error: Failed preliminary check by password service

but I have no clue what the check I've failed is, or if it's a console
problem (locales, weird control characters) or maybe a selinux thing?

For the record, if I enter a weak password on purpose, e.g. "amok",
everything works, meaning that I get an explanation like "password
refused because it's too short", or something like that. But when I
try longer passwords, with or without non alphanumeric characters, I
get this error.

what else should I check, or fix?

TIA,
Marco