This started with 1.4.3. When you are creating a world, (or re-recreating it), the player gets stuck in the block that spawns underneath them. Re-spawning does not exhibit this issue.

What I expected to happen was...:
I expected to spawn in the new world after the creation screen and be able to move to my next objective.

What actually happened was...:
I spawned in the world and was stuck 'bobbing' or otherwise 'floating' as if I were stuck on the block below me. You have to destroy the blocks 'holding you in place' in order to regain your movement. Most of the time it is the one below you, occasionally it may be a tree.

Steps to Reproduce:
1. Start a new world
2. Watch map load really slowly until you finally have land to stand on
3. Your character is stuck bobbing in the block below you and it has to be destroyed to continue

Other Notes, probably important:

I noticed on my computer when loading Minecraft, the map initially used to generate instantly in prior versions. Instead, this time it seemed like it starts with a totally blank world with just a sky, no chunk and then the map suddenly generates a few seconds later. In fact, there was one time I generated and kept falling and taking 'wall damage' until I finally died. Eventually I re-spawned and the issue did not reproduce so I can only assume it has to do with laggy map/chunk generation. Most of the time this happens, I just get stuck and somehow 'tethered' to the block below me. It's almost like my character is wanting to fall, but the block beneath is holding it in somehow? It's an odd animation because it doesn't appear as though you are stuck in the block below you.

**This doesn't occur 100% of the time, but does most times. It appears to only happen when the map takes a longer than normal time to generate.

I added a video to show what I was talking about