Time Machine not starting when I connect the HDD
(Edit: Lion makes this less of an issue with local snapshots possible as well as the ability to script the starting with tmutil startbackup - the rest of this answer is in regards to Snow Leopard implementation of TimeMachine)

Time Machine sets a timer based on when the mac is booted, so it's very unlikely the system looks to start a backup when the device is attached.

Instead, it is designed to commence a backup periodically and will log messages and skip a backup if there is a problem or the drive isn't attached. Once one or more backups gets skipped, perhaps it might start one sooner when the volume it expects is attached. I just checked on one mac that backs up to a local disk. When I log out all users, it doesn't see the disk at attached, so it skips each back up. When I log back in, that user log in mounts the disk and Time Machine started a backup immediately rather than waiting the "rest of the hour" for the backup.

This is how it is supposed to work.

I would initiate a backup using the control panel or the menu item to be sure there isn't an error condition - but once you rule that out, it's just a matter of time until the hour passes and your backup will start.

Have you made sure there isn't some other issue by checking in the console app? Also, do you let this mac sleep, or will it stay running for several hours and still skip a backup when the drive is connected?