Correct solutions came from Ron Welch, USA; Philippe Fondanaiche, France; Heidi Meyer, USA; Jens Voβ, Germany; Brett Hendricks, USA; Farid Lian, Colombia; Claudio Baiocchi, Italy; K. Sengupta, India; Lou Cairoli, USA; J. Rast, USA; Juan Carlos Marivela, Spain; Nathan Faber, USA; John Snyder, USA; Lou Cairoli, USA. 

Subtracting an appropriate value k from each entry of an n ´ n magic square, leaves a standard magic square with entries from 1 to n².  The common sum of a standard n ´ n magic square is n(n² + 1)/2, so 2006 - kn = n(n² + 1)/2 and 4012 = n(2k + n² + 1); therefore n must divide 4012 = 2²·17·59.  On the other hand, k is a non-negative integer, so 0 < 2nk  = 4012 - n³ - n which implies n³ < 4012 < 4096 = 16³; therefore n < 16, its possible values being 1, 2, 4.  A (degenerate) 1 ´ 1 square obviously exists, the 4 ´ 4 case is POTW 249, and you can easily show no standard 2 ´ 2 square exists.