not sure about earlier versions, but recent photoshops can choose from 3 different behaviours in the way it selects the 16 colour palette. it's worth trying the different methods rather than just going with the default