You should test using the default checkout process.
Go to your system->config->design and choose the default package and default theme.
The problem is most likely your layout files.
If it still does the samething try changing your package to RWD. This will ensure you don't have any changed template files.