高速なマップスクロールについてはやねうら本に書いてあったような。

ハードウェアアクセラレーションが効いていない場合が考えられるので、
しんさんの出張所(日記)　とか読んでチェック汁

あと、VMのご機嫌とるのマンドクセな場合は、↓を使うとか．．．
Java Binding for SDL
http://sourceforge.net/projects/sdljava