Yes, that's correct!
Your iPhone, if the newer 3G model would require iTunes 8. If you have OS X 10.3.9, then you need to upgrade to 10.4.11
That's not a free download to upgrade, so you will need an installer disk to do that.
Did you have 10.4.x before your reinstalled your system this time?
You would need to upgrade to 10.4 the same way that you did before.
Perhaps you have the 10.4, or Tiger upgrade disk, or you have the full install of Tiger, which would be a black label DVD...