Brew says Wine is installed but it fails to run with "command not found" error
If it is a simple problem then brew unlink wine and brew link wine might resolve it. This isn't the same as uninstalling and reinstalling, which would be brew remove wine and brew install wine. It should be quite quick.

When brew installs a piece of software it installs it to /usr/local/Cellar and then links it to /usr/local/bin. Unlinking just removes those links, so it is still there but basically sitting somewhere it wouldn't normally be found.

But the first thing to try would be to check that /usr/local/bin is in your path. You can check this by typing echo $PATH in a Terminal window. You should see something like /usr/local/bin:/usr/bin:/bin:/usr/sbin:/sbin:/usr/local/bin.