If the remotes are brand new, then it can't be the remotes that is the problem. Mybae you skipped a step or aren't going through the steps correctly. Click the link below and try the instructions if you haven't done so already...

http://handaaccessories.com/crv/KEYLESSPROG.pdf