a) We look at the projections of painted black squares onto coordinate axis. Denote the lengths of these projections by $a$ and $b$. In such case area of all squares with marked sides does not exceed $ab$, and the number of black sides of squares is at least $2(a+b) \le 2006$ (it is easy to see that there should be either zero or at least two painted black horizontal lines in any column and the same for any row). Whence the required number of repainting does not exceed $ab \le \frac{(a+b)^2}{4} \le \frac{1003^2}{4} < 260000$.

b) Let's assume that all squares that should be repainted odd number of times are marked with blue color. Then in the initial arrangement only those sides of squares are painted black that neighbor one unmarked and one marked blue square. We get the least possible number of repainting if each square, marked blue, will be repainted only once, and unmarked squares won't be repainted at all. Let's estimate the number of squares, marked blue for the following initial painting: the perimeter of the $501 \times 502$ rectangle. There are at least as many marked squares as the area of rectangle is. And this area is equal to $501 \times 502 > 250000$.