直接の回答はできず申し訳ないのですが､というのは､まず仕様が混乱しているうちから実装方法の議論を始めても仕方がないからです｡
↑で順位がひとつ上がると考えたのに､実例では↑で最上位まで上がってしまっています｡ひとつ上がるのと最上位に上がるの､どちらが正しい仕様ですか？
また､新ｴﾝﾄﾘ追加の際にどういう順位ﾃﾞｰﾀを与えるべきか､それを考える前にまず新ｴﾝﾄﾘは表中のどこに出現してほしいのか､そこを決める必要があります｡

単純に､

としておいて､↑や↓の操作で､上下のﾎﾟｼﾞｼｮﾝ値を入れ替えればいいんじゃないですか？


それだと､追加したものは最大値＋1にしておけばいいですし､
二つのﾃﾞｰﾀの入れ替えだけなので､手間もそうかかりません｡


仮に､test4を一気に一番上にするとか､test1とtest2の間に(1ことばし)とかいう
操作が必要なのなら､別途検討だとはおもいますが｡

方法は大きく2つくらいでしょうか･･･

(1)ﾃﾞｰﾀ件数が非常に少ない場合

関係するﾃﾞｰﾀの position の値を全て書き換える

(2)ﾃﾞｰﾀ件数が多い場合

position ではなく 通し番号No､前preNo､次nextNoの情報を用いる｡

下記では､最上位に来るﾚｺｰﾄﾞは preNo = 0 として､
最下位に来るﾚｺｰﾄﾞは nextNo = Null(未定義) とすることで､
それぞれ基点と終点を表すこととしています｡

No.3(test3)を最上位に移動させる場合のﾃﾞｰﾀ修正は次のようになります｡
1. preNoとnextNoがNo.3になっているﾚｺｰﾄﾞのpreNoとnextNoを修正
2. preNoがｾﾞﾛ(すなわち最上位)のpreNoを修正
3. No.3のpreNoとnextNoを修正
ﾃﾞｰﾀが何件になろうとも､修正するのは常に4ﾚｺｰﾄﾞ分で済むため､
ﾃﾞｰﾀが多ければ多いほど(1)との処理速度で比較にならないほどの差が出てきます｡
新しいﾃﾞｰﾀtest5を追加する手順は次のようになります｡
1. nextNoがNullのﾚｺｰﾄﾞを探す
2. 新しいﾃﾞｰﾀNoを 5 に決定する
3. Null を 5 に書き換える
4. 新しいﾃﾞｰﾀを書き加える
位置変更も新しいﾃﾞｰﾀ追加も､
途中でﾄﾗﾌﾞﾙ停止になると順位がおかしくなるので､
最後まで正しく修正が終わらなかった場合を想定して､
変更前にそれぞれの値を別の場所に保持するようにして､
元に戻すこと(ﾛｰﾙﾊﾞｯｸ)ができるように､
ﾌﾟﾛｸﾞﾗﾐﾝｸﾞしておくべきでしょう｡

順位を表す数値を､初期値としては100とか1000ずつにして､変更するときは挿入する上下の間の値に変えるという方法もあるかと思います｡
例：
初期値

test3を1つ上の場合､前二つのtest1とtest2の値を取得して､test3をその間(平均値)の1500にする｡

この状態でtest2を一つ上なら1250､一つ下ならtest4の下はないので4000+1000､test3をもう一度上ならtest1の上がないので0との間をとって500 とか､新規追加はmax+1000とか｡

利点はその時点での更新ﾚｺｰﾄﾞが1つで済むこと｡おそらく並べ替えの実行より圧倒的に多いであろう､並び順のﾘｽﾄ取得が行いやすいことなどがあります｡
欠点は何度も並べ替えると間が詰まってくるので､番号を振りなおす処理を適宜(あまり頻繁ではｺｰﾄﾞが複雑な割に毎回振りなおすのと変わらなくなるし､あまり遅いと､その間に入れる間隔がなくなってしまう可能性がある)行う必要があるとか､間がない場合の例外処理が必要だとか､ｺｰﾄﾞの流れが単純でなくなることでしょうか｡

番号振り直しのﾀｲﾐﾝｸﾞは､例えば並べ替え時に間隔が100以下になったら､例えばdirtyﾌﾗｸﾞ持たせるとかｷｭｰに入れるとかして､cronで回して……とかありますが､あまり凝った事をするとﾊﾞｸﾞの要因になりますし､他の方法も含め､ﾘｽﾄの数や他の部分の規模との兼ね合いかなと｡

[追記]
ﾃﾞｰﾀﾍﾞｰｽ上での逐次並べ替えという流れでしたが､javascript使ったUIも視野に入れ､ﾌﾞﾗｳｻﾞ上で並べ替えを行い､決定した段階でｻｰﾊﾞに送信､ﾃﾞｰﾀﾍﾞｰｽを更新という流れならば､ｻｰﾊﾞｻｲﾄﾞでは+-など演算を考える必要なく､送られてきたﾘｽﾄに従い順番に順位を更新するだけでよくなります｡
http://alphasis.info/2011/05/jquery-ui-sortable-submit/