Does hook_node_access_records() and hook_node_grants() change permissions for existing nodes?
You can implement hook_enable() and call node_access_needs_rebuild(TRUE), see user_relationship_node_access_enable() for an example.

That doesn't actually do much on its own, but Drupal will then automatically print a message to administrators and inform them that the permissions need to be rebuild and also includes a link to the place where this can be done.