The usage note for denote in the AHD4, I think, is good, as are the examples we've been given here by various AWADdies. What we need is a good mnemonic for remembering which is which.

Denote just sounds more 'pointy" to me; connote has more of a sidelong feel to it.