The skill description states "Tumble at one-half speed as part of normal movement..." (emphasis mine).
I checked out the FAQ on the wizards website, and they talk about tumbling while prone, and loosely define "normal movement" as movement currently allowable - in the case of prone, crawling at 5' - but because tumbling is done at 1/2 speed, they have would have to accept the -10 penalty for "accelerated tumbling" to tumble at "full speed" since you can't move half a square.
In the case of withdrawal, a character can move up to double her speed (the first square does not count as threatened - but this question isn't about attacks of opportunity, but about movement distance). If I read literally from the skill description, this means that the player can elect to tumble for part of that distance, but the distance tumbled counts as double since tumbling is done at half speed.
So, for instance, a character with a move of 30' can make a withdrawal move action, tumble for 3 squares (15 feet) and then move at normal speed for 6 squares (30 feet - assuming straight lines of course, since every second diagonal costs 2 squares) or any combination so long as tumbled squares cost double.
Does this seem like a reasonable interpretation?
As an aside, can Tumble be used in a charge action?