(This is on MMA 7.0.1.0 on OS X)
I've just found a large matrix m for which NullSpace[m] and NullSpace[m, Method->"OneStepRowReduction"] give different answers (the first one is the correct answer).
I put the matrix up at pastebin as won't fit here!
What's going on? How might I guess ahead of time which arguments are going to break Method->"OneStepRowReduction"?
(Update; it seems the bug has got worse in 8, rather than better.)