What usually works for me is to actually right click a file type you want the app (in this case, Photoshop) to be able to open from that "open with" menu and then from the "Open with" menu, select "choose default program" and browse for the .exe of the application you want to have on the menu (i.e., Photoshop) that is not currently there and select it. But make sure to uncheck the box to make this the default application for opening that type of file. After that, that program (in this case Photoshop) should always appear in the list when you use open with on a file of the type you just used for the above procedure.
I hope that explanation is understandable. I did manage to add photoshop and several other apps to the list that way.
