Sounds like you are stepping them too fast for the current you put through them.
How are you driving them?
What current have you set your driver to?
What voltage are you using to drive them?
What is the resistance of the coils when measured with a DVM?