It probably is only happening on characters with wrinkles. After skin color changes the wrinkles need to be rebuilt. Following these steps should fix the issue:
1. Select the wrinkles tab in the modify panel.
2. Click the trashcan button to delete the current wrinkle maps.
3. Check the "Activate Expression Wrinkles" box to generate new wrinkle maps.