Good news - I did a hardware reset and this has fixed the issue. At least, it has as of now - hoping it doesn't return. But as of now it is working consistently, whereas before the hardware reset I couldn't get it to work at all.
Here's a quick recap. I got a new controller since I wanted the Dual Shock anyway. Plugged it in to the USB and saw it work, then disconnected it from the USB and just got the blinking lights. This ruled out my other controller as the culprit.
Then I performed the hardware reset as instructed by the Sony rep on the phone. To do this I turned off the power switch on the back of the PS3, then placed my finger on the "soft" power on button on the front of the unit and kept it there, while turning on the PS3 with the switch in the back. I kept my finger there until I heard two beeps and the unit shut itself off. Then I press the soft power on and it came on, and I had to plug the controller into the USB so I could reset some options like HDMI. It asked a few set up questions and then was done.
Then I disconnected the controller and viola, it worked!! Then I plugged my other controller in to the USB, go it to sync, disconnected it, and that one worked too.
I then spent some time wirelessly turning the PS3 on and off using each controller and it worked every time. I also turned the controllers on and off just fine.
So, for now at least it is working. And at least this is a rather quick fix so that if the problem resurfaces every now and then I won't mind too much doing the hardware reset. Certainly it is faster than the mucking around I would have to do before to try and get the controller to work.
Now another thing - this proves that it is a SOFTWARE issue/bug with the PS3. And I'm guessing it was perhaps introduced with a firmware update at some point. This gives me some hope that eventually, with enough people complaining, Sony can track it down and fix it once and for all. Certainly I am very happy I didn't have to send the PS3 in for service despite still being under warranty.
I hope this helps others. Note that there are likely multiple causes for sync issues so perhaps this will help some folks but not all.
UPDATE: Well I'm disappointed to say that things are back to not working, yep, just that quickly. I fired up a Blu Ray and while watching the movie the controller timed out. Then when I hit the PS button on it it just blinks and will not resync. I then took the other controller that hadn't been in use and tried to turn that on, and the same thing. The frustration continues. This definitely stinks of a software bug.