And if that doesn't work...
Does you device confirm that it's getting the policy (Options>Security>General I think, from memory)?
Create a copy of the default poolicy, send that to the device and see what happens.
I was a BES and Exchange admin once.
Then my world turned Blue.