You must reteach the user frames that is for sure. My guess is that you taught them by jogging the robot to a fixture and then save the position to a PR and declare the User Frame = PR[x].
If this is the case, then you must check the configuration of the taught position before you store it to the PR.
As a rule of thumb, when I teach a user frame to a fixture I am always using NUT 0,0,0 config before I store the position to a PR and declare the frame.
As a second rule of thumb, I always take into account what my Home position's configuration is. The reason behind this is that all of my programs start and stop at home position, so if for example my user frame is FUT 1,0,0 and my home position NUT 0,0,0, then the robot will start from a NUT 0,0,0 config, proceed to a program on a frame with different configuration which means a lot of unecessary posture changes and rotations then return to home position (meaning bringing back any rotations to 0 and config change again) then proceed to the MAIN program for pick/place/palletize which again has different User frames.
I always "tie" my user frames to my home position config. A lot healthier for the robot and a major reduction in cycle time.