If it wasn't a loose cog, here's something else to consider.
You mention a new cog, but what about your chain? If you're running an old chain, it may be worn to the point where it isn't meshing correctly with the new cog teeth. You only find out when applying high loads, then it skips.
To know if your chain is "stretched," measure a 12" length. Center or edge of one link pin should line up at the exact same spot on a corresponding pin 12" away. If your chain is more than 1/8" longer over a 12" length, time to replace the chain.
However, is chain skipping that common on fixies? It happens all the time on geared bikes, where there's excess chain length to accommodate the chain lifting off the cog and slipping forward one or more cog teeth.
I'm not a single/fixed gear type, so can't rely on experience like with geared machines.