I strongly disagree. I understand WotC wants to sell its online package of stuff, but it should not be required from a physical product. Everything you need should be in the box labeled "Starter set".
Also not thinking if those kids that can afford the starter set can even use the character builder due to the high-end requirements of the complete package it is built around.
The PHB does not require online services, nor should the starter box.
An advertisement for DDI is one thing, but trying to force a sale due to neglected information or require an additional purchase is just downright offensive to me.
DDI and the physical products should not be tied so closely together no matter how much they are both wanted to be sold. You don't need DDI to play D&D, and many cannot use it due to system requirements not including OS.
I cannot get behind thinking the DDI tool is OK to satisfy the lack of presence of character generation in the starter. It seems like saying you had to buy E-tools, or Master Tools, or whatever for 3rd, or AD&D core rules for 2nd edition because the starter left them out. It just really dismays me to think that is the case.
The Rouse has been saying, however, that the Character Generator will be free for levels 1-3: so it's not exactly a money grab. If beginners want to dabble in character generation then there's a free option for them before they get their hands on a PHB: however, it's debatable how they'd know to do such a thing without the starter set telling them to. (And that's ignoring your comments about system requirements, which are a more DDI specific complaint that I'll leave for anotehr thread)
Back to the more core topic at hand: Everyone hoping for a product exactly like the old Red Box is perhaps forgetting that the whole reason they dropped the BD&D line was the market fragmentation that occured from having it and AD&D alongside each other - in a similar vein, notice that Wizards also no longer make a dedicated beginner Magic set in Portal, instead packaging up their "real" product in a beginner friendly package.
Furthermore, to the people asking for an "all-heroic tier" product.... well, as someone else said, that's a huge amount of words, since heroic-tier is the one with the most material on it. The scale people are asking for, especially at a beginner-friendly price point, is just unfeasable.
Now, I do agree that some sort of character generation is a pretty key RPG trick, and think the 3.5 black dragon box set is all the better for having it in a limited form. Then again, I bought a copy of that box for a little cousin for his, um, 14th birthday, and it was a hit with him and his little siblings, and they were keen to play again and happy when I bought him a PHB proper for Christmas, they never made their own characters with the boxed set.
A starter set for D&D should certainly have pre-generated characters and possibly a link to a website where there could be more pre-generated characters available to give it a quicker start-up time. Having some sort of optional rule for character creation in the back would seem a good idea to me, so there's a middle ground between "newbie playing game for first time" and "time to buy my PHB", but I dunno how much of that would really be appreciated by the target 10 to 12 market.
At the risk of invoking e-tools, what if the game also came with a CD that contained PDFs to print of all the character sheets, monster stats etc, and a little tool to design your own 1st level characters from a limited palette? There's still a cost issue in designing that, but if you already have a DDI tool on the way, it's a pretty trivial addition - and even without a character generator, being able to print out rather than have to tear or photocopy the sheets seems a pretty key thing that a modern gamer would expect.