You know, it's strange, but I find I can't even picture what the game play was like. It was a long time ago, but my gut feel (appropriately) is that it wasn't even a first-person shooter. But either way, head-bob hasn't had any notable effect on me in any other game. I mean, I'm not hugely keen on the effect. It feels .... artificial .... to me, but it's never made me feel even mildly icky, let alone killer migraine.
There was something about that one game that I've never experienced in any of the hundreds of other games I've played over the years. I've just no real clue as to what it was.
EDIT - Thinking about it, I THINK it was the original Castle Wolfenstein that did it, and that was top-down 2D. But it might have been Wolfenstein 3D, which was a very early FPS. Either way, I loved playing it, which was why the effect it had was such a PITA.