The above is outdated but the troubleshooting steps remain applicable. Try restarting using OS X Recovery.
Time Machine requires sufficient space to create a complete backup of your entire source volume's contents. It will require more than that to be useful, but does not necessarily have to be equal or greater than the source volume's size.
To exclude items from Time Machine backups, use Time Machine Preferences and select the Options button.