It is possible to have both setup/hold violations on the same reg2reg path: if you have big "delta delay", which is due to big coupling capacitance on some nets in the path. During setup analysis, the tool add this "delta delay" to the total path length (so you may have setup violations). During hold analysis the tool sustract "delta delay" from the total path length.
Try to minimize the coupling capacitance (increase wire spacing or change the metal layer).