ReplacePart, MapAt, Inset can be very slow in Version 4.0 or Version 3.0. They are probably just as bad in Version 2.2, but I didn't check.
Consider the expressions:
ReplacePart[expr, 1, lst]
MapAt[f,expr, lst]
Inset[expr, 1, lst]
Where (lst) has the form {{__Integer},{__Integer}, ...] and Length[lst]=n.
In that case each of these functions are O[n^2]. For those who aren't familiar with this notation, O[n^2] means the evaluation time is proportional to n^2. Hence if (lst) is a long list of lists these functions are very slow.
TestReplacePart[n_]:=Module[{size,p1,lst2,t1},&IndentingNewLine;(size=250*2^(n+1);&IndentingNewLine;p1=Union[Table[{Random[Integer,{1,size}]},{size/2}]];&IndentingNewLine;lst2=Table[Random[],{size}];&IndentingNewLine;t1=(ReplacePart[lst2,1,p1];//Timing//First);&IndentingNewLine;{Length[p1],t1})&IndentingNewLine;]
Table[TestReplacePart[n],{n,5}]//TableForm
| 395 | 0.04999999999999982` Second |
| 780 | 0.21999999999999975` Second |
| 1580 | 0.9299999999999997` Second |
| 3108 | 4.009999999999999` Second |
| 6276 | 18.12` Second |
TestMapAt[n_]:=Module[{size,p1,p2,t1},&IndentingNewLine;(size=2 Floor[250*2^n];&IndentingNewLine;p1=Union[Table[{Random[Integer,{1,size}]},{size/2}]];&IndentingNewLine;p2=Table[i,{i,size}];&IndentingNewLine;t1=First[Timing[MapAt[#+8&,p2,p1];]];&IndentingNewLine;{Length[p1],t1}&IndentingNewLine;)]
Table[TestMapAt[n],{n,5}]//TableForm
| 396 | 0.060000000000002274` Second |
| 782 | 0.269999999999996` Second |
| 1593 | 1.259999999999998` Second |
| 3191 | 5.490000000000002` Second |
| 6272 | 24.28` Second |
TestInsert[n_]:=Module[{size,p1,p2,t1},&IndentingNewLine;(size=2 Floor[150*2^n];&IndentingNewLine;p1=Union[Table[{Random[Integer,{1,size}]},{size/2}]];&IndentingNewLine;p2=Table[Random[],{i,size}];&IndentingNewLine;t1=First[Timing[Insert[p2,1,p1];]];&IndentingNewLine;{Length[p1],t1}&IndentingNewLine;)]
Table[TestInsert[n],{n,5}]//TableForm
| 237 | 0.060000000000002274` Second |
| 472 | 0.10999999999999943` Second |
| 951 | 0.4899999999999949` Second |
| 1879 | 1.980000000000004` Second |
| 3786 | 8.399999999999991` Second |
It seems like there must be algorithms for (ReplacePart, MapAt, Insert) that would evaluate much faster with a long list of parts. It may be that the developers used slower methods which are needed to ensure that the result is correct. A similar issue had to be addressed with Union. However, in the case of Union the developers decided to use a method that is O[n Log[n]] and they accepted the risk that the result might include some duplicates.
At http://support.wolfram.com/Kernel/Symbols/System/Union.html we see Union treats elements as duplicates only if they appear in adjacent positions after sorting. Apparently this method is O[n Log[n]], and Union would be O[n^2] if it compared all pairs of elements.