The oldest "rumor" report I could find in a quick web search was on BGR, October 3rd of '07.
Search the web for "BlackBerry 9000 whispers in our ear" for their entry, which included a shady image. I'll bet it was on RIM's drawing board for a few months before this info was made public.
The other half of this question might ask, "when was it complete?"
Sure, it launched last week in the UK, but at some point (weeks? months?) prior to that RIM finalized the design and had the factory begin cranking them out, in order to meet the quantities necessary to distribute for launch.
I figure that in itself requires quite a bit of lead time.