Have you checked the obvious?

Firstly, without the stepper motor connected, single step the logic and check the outputs - I assume you have a truth table. Using a pushbutton or switch to create the clock is fraught with problems as the contacts bounce - this can cause the symptoms you describe. If using a switch add a debounce circuit - search web for suggestions. If using a micro have it generate the pulses. Handy hint use the printer port of your PC for some outputs and write a little program in VB or whatever to generate a pulse when you click a button.
After doing this you show have verified your logic.

Reconnect the motor - repeat the tests. If the logic is getting scrambled you have induced noise problems from the motor - check wiring of 0V and add a few caps on the power rails.

Assuming logic is still ok, have you wired the motor correctly? Swap motor phases to check.

If all else fails - find an old 5 1/4" floppy disk drive full size like the in the original IBM PC (TANDON TM400). Reverse engineer it's stepper circuit to find where you went wrong. Careful - this involves a little effort!!!

Net result is you should have a stepper circuit that works and have learn't something in the process.

If you are using a micro in your project - have it generate the step sequence. Have a table of the step sequences and output the to the port then to the driver chip. You can have full step or half step just be changing the table. Step thru the table backwards to reverse the motor - simple!