Cannot keep up error with my setup also. I can run the game with optimal graphics on vanilla textures, but horses stutter a lot.
FPS and rest of the world is unaffected. FPS is 45ish during testing, no anomalies. During horse stutter, other mobs (sheep, cows etc) are not affected.
Every time new chunks are generated, the horse stops and won't move until chunk generation is complete.
Horse works normally when in pre-generated areas.
edit: Windows 7, Java 7, MC Version 1.6.1 pre-release singleplayer
Problem persists in 1.6.2, with or without horse armor.
Reproducible just by creating a new world, spawning a horse, taming it, placing a saddle and traveling to ungenerated chunks.
No movement stutter while player character is on foot, even with speed boosts.