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\Aplications. Find the name of the program you are trying to use (probably photoshop.exe or something similar), and browse to \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\Aplications\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.