RUS and migrated users

Hi all,
I am having a problem getting my head around recipient update services on Exchange 2003. The policies are not applying to any users that I migrated from our previous nt4 domain to the new server 2003 AD. For some reason, But I cant seem to figure out why?? I have followed the instructions in this kb article: http://support.microsoft.com/kb/254030/en-us, but I have the "allow inheritable...." box ticked in the OU that they are based in and each user also has the "automatically update email address based on recipient policy" box ticked. I am almost certain it is to do with permissions but since I havent changed any from the default. All help would really be appreciated