Sometimes a headset will feel OK if you just turn it by hand.....Try applying the front brake and then pushing back and forth on the bike while holding your thumb on the stem or headset. If there's any play you should be able to feel it.
You might check the front wheel bearings while you're at it, though it certainly sounds like the headset. Fixed-gear should have nothing to do with it.