I tried march=native, it didn't do any better than just using SSE2 for me.
Specifying all the SSEs as well as AVX (I was using a 2600k) made a big difference.