I dont know what happened, but all of a sudden it started working. I did not touch the job and it had refused the client side dedup over and over again (the job runs everyday) and then all of a sudden it just started working.
I also can not get client side dedup to work on a VM (like you I have the remote agent installed on the VM) and no matter what I do, I can not get it to work.