Let f(x) = g(x) + 2x - 1. Since f(1)=1, f(2)=3, f(3)=5, f(4)=7, f(5)=9 and 1,2,3,4,5 are all the 5 roots of g(x), then follows that g(1) = g(2) = g(3) = g(4) = g(5) = 0.
Since f(x) is 5th degree with leading coefficient 2009, the same is true for g(x).
Therefore, g(x) = 2009(x - 1)(x - 2)(x - 3)(x - 4)(x - 5).

So now, we have
f(x) = 2009(x - 1)(x - 2)(x - 3)(x - 4)(x - 5) + 2x - 1
f(6) = 2009(5)(4)(3)(2)(1) + 12 - 1 = 241091

f(7) = 2009(6)(5)(4)(3)(2) + 14 - 1 = 1446493

f(8) = 2009(7)(6)(5)(4)(3) + 14 - 1 = 5062693