I have had this happen in my organization after all our users were bound to active directory (effectively changing the UID from 50x to ######).
Now it is simply a case of changing the ownership of all files where were owned by x to y.
Where 501 is my old numeric user id which is still associated with all the homebrew files.
The old user id can be found using ll /usr/local/Cellar
Now update the ownership
sudo find /usr/local -user 501 -exec chown -h $USER {} \;
This way we avoid changing the ownership on files which are not controlled by homebrew or belong to some other system user.