Ok, I've found a workaround on another thread (
http://discussions.apple.com/thread.jspa?messageID=9658855).
According to that poster (he has an iPod Touch), Apple Tech Support told him to disconnect his computer from the Internet, and then try to connect his iPod Touch. This worked for him. I just tried it and it works reliably.
After reading the post I plugged out my Internet connection from my laptop, and then connect my iPhone. It was detected. I repeated this 4 more times and each time the device was detected and came up in my iTunes sidebar. I then restarted my machine and tried it again 5 times. It worked all 5 times. When I reconnected my machine to the Internet, the problem came back the very next time I plugged my phone in.