I am going to assume you are using Active Directory for your Policy since you are mentioning OU's.  There are a couple of factors that can affect policy resolution in this case.  1.   AD synchronization.  If you have more than one domain controller, the one being used for policy has to be in sync with the one where the computer account was created\moved, sometimes there is a delay and the policy manager looks up the AD info the agent gives it and gets a different response.  I believe this is usually an 843 error in the client log. (or maybe 650).     2.  The other scenario is policy resolution caching. The policy server may be using cached information for a period. (there is a config setting).    How long did you wait after performing the AD add\move, prior to running the notify? 

Yes, I'm using Active Directory. Im only using one DC though. And I was trying for about 1.5 days. After I switched back to the original container, I did the notify immediately after and it didnt fail.  There's just something it doesnt like being in a different OU.

The LDAP directory service has a base DN in its configuration.  If the Computers container is your base DN then the policy resolution would not work outside of it? 

To add on to Derrick's initial comment and to respond on some of the feedback so far the base DN define in the Directory Services Connection Setting window is  at the top of the domain. For example dc=<domain>,dc=ad,dc=company,dc=com. Our AD structure at this point will have different OU'S based on the country so we will have multiple OU's for setting entitlement.