I have had the intermittent "need to put to sleep twice" issue since my very recent 10.6.5 upgrade. For me, the problem seems to be an external disk drive that refuses to sleep right away and/or a hard drive from another iMac mounted over the network. (My keyboard and mouse are wired.)
One thing I tried beyond what is listed in the below help files is to go to Spotlight Privacy in System Preferences and turn off indexing for my external and network drives. (For example, indexing backup disks seems wasteful to me.) It's tricky to declare success since the problem is intermittent.
Try reading these:
* "If your Mac computer won’t go to sleep or stay in sleep"
http://docs.info.apple.com/article.html?path=Mac/10.6/en/9040.html
* "Mac OS X: Why your Mac might not sleep or stay in sleep mode"
http://support.apple.com/kb/HT1776