I experienced a similar problem with an XP box a few months ago. After clicking "open with", then browsing to the application I wanted to use, the application still failed to show up in the "Open with" menu. The cause may not have been the same, but here is what I had to do. Warning: if you are not comfortable manually editing the registry, this solution may not be for you.
Open the registry (regedit.exe) and browse to
HKEY_CLASSES_ROOT\Applications
Find the name of the program you are trying to use, e.g.:
HKEY_CLASSES_ROOT\Applications
\Photoshop.exe
and browse to
HKEY_CLASSES_ROOT\Applications\Photoshop.exe
\shell
\Open
\command
The "Data" value of the default key will be the path used to launch the executable when opening a file. For example, on my machine
HKEY_CLASSES_ROOT\Applications\EditPadLite.exe\shell\open\command
contains the value:
"C:\Program Files\JGsoft\EditPadLite\EditPadLite.exe" "%1".
In my case, the path was pointing to the wrong place, and I had to manually correct it. Afterwards, the "open with" dialog worked as expected. It may be the case that the path is pointing to the 64-bit executable for you, and redirecting it to the 32-bit exe might fix the problem. Make sure to back up this key before you make any changes!
I regret that I do not have photoshop on this machine so I cannot tell you exactly what the path will be, but hopefully it is similar to the one I showed. I hope this was helpful.