If you think of the phases of the stepper, it would go from [--] to [-+] to [++] to [+-], and then repeat.
If we label those phases as:
[--] J
[-+] K
[++] L
[+-] M
Then you go "forward" by stepping JKLMJLKMJLKM... and "backwards" by stepping MKLJMKLJMKLJ...
If you flip the bit on both, we now have:
[++] J'
[+-] K'
[--] L'
[-+] M'
So when you drive, you get J'K'L'M'J'K'L'M'... But J' is really L, K' is really M, L' is really J and M' is really K on the motor, so you are moving LMJKLMJKLMJK... which is the same sequence of the "forward" stepping, but with the cycle starting half-way in the middle of the original cycle.
So, yes, if you reversed the polarity on BOTH coil sets, you would still move in the same direction. However, you will be off by half a stepper revolution. Depending on the gearing, the difference would probably not make a difference.
EDIT
I updated to indicate polarity as +/- (versus 1/0 in my original posting).
This is easier to visualize graphically -- if you treat each winding 1 as the X coordinate, and winding 2 as the Y coordinate, then you are stepping between four quadrants. If you then half- or quarter- step, you are just increasing the number of points that define your loop. Taken to the limit, if you have the X=sin(wt) and Y=cos(wt), you'll have a smooth circle; and if you reverse the sign of one (say X=-sin(wt)), you'll just go through the circle in reverse direction.