Which version of photoshop is it? Also is it the same problem with other file types like jpg? Lastly, besides the double click association are you able to or not able to drag and drop a PSD onto an open photoshop?
There is some subtle change in DDE I've noticed that prevents some programs from opening files via association or even drag and drop. I.e. Visual studio even WITH the updates. I believe that CS5 works fine with Windows 7 but earlier versions may exhibit the problem.
If the answer to all the questions at the top are "no", and your on an older version, then it may not be fixable without an update to photoshop.