It's a geared stepper, which means that it's a stepper (64 steps, I gather) followed by a 64:1 (approximately) gearbox. What you're seeing is almost certainly backlash in the gear train (see where I "suspect a poor mechanical joint..., below). Any gear motor, stepper or not, is going to have backlash. Because there's a tradeoff between the precision of the gears and how much backlash you can get out of the assembly before the thing binds up, a cheap motor is going to have more.
If you can preload the motor with a constant torque that only points in one direction, then you could reduce the backlash (although maybe not eliminate it, given the amount of gear reduction and the cheapness of the unit). If you need more precision that that, then you're going to either need a direct-drive stepper (which, thinking about, is going to be hard to find with that many steps), or possibly a geared stepper with a much higher precision gearbox, or you're going to need something like a bazillion-pole brushed or brushless "regular" motor, position feedback, and a controller.
(Former answer left in because it's valid for a direct drive stepper, if you find one with 4096 steps).
How much motion are you seeing? Just by the way that the magnetic circuit is designed, you should expect some motion within a step (in an unpowered motor it's not terribly inaccurate to think of the rotor as being connected to the frame through a spring, at least until you overcome the motor's holding torque).
If there's more slop than that (which works out to less than 1/10th of a degree in your case!) then I'd suspect a poor mechanical joint between rotor and shaft, which is just wrong. Did the motor come from a reputable source?
