Spent about 4 hours looking for horses on a multiplayer server but was unable to find any. Tried checking old and new chunks. I went through at least 10 different plains without seeing one horse.
I am able to find them on singleplayer worlds almost immediately.
Same for me.
Played a world in 1.5.
Explored a full maximum zoomed map.
Updated server to 1.6.2.
Couldn't find horses.
Then recreated the map with the same seed in single player mode.
Instantly found horses in the first plain biome.
Seems like horses can not spawn in plains genereated before 1.6.
Best Regards