Players on my SMP server get odd lag

Before the horse update, this kind of lag did not happen. After the update, players on my minecraft server are experiencing a different kind of lag. They are experiencing block lag for the first ten minutes when they log onto the server, and sometimes even fall in the void when they log in for periods of time. This does go away after ten minutes or so, but it is very difficult to play on my server because of this. Please look into this.