My company just fixed this. By requiring you to change your password by more than the last character. Really cutting edge security here.
3password
4password
...
>=]
Anything below 5 in distance gets rejected, try again, please.
While you get to change password you make 2 boxes with current and new of course and do your comparisons on it, just to explain you still keep passwords hashed.
password02february
password03march
...