I was on an online chat w/Pat Goss (Motorweek) and his comment was "Check the lock solenoid (brake shifter interlock), solenoid adjustment, and brake switch."

To all you experts out there...would one of these make more sense if the problem only happened when it's cold out?

I have accomplished one thing though - while driving I knocked the pen (which we use to disengage shift lock) hard enough to break off the spring loaded tab, and get it jammed in the hole. Luckily I was able to get it out, now there's just a hole...

..sigh...