Update: Still not working, however I notice a difference on this installation where it isn't working. If I click the Youtube link in Video Quicktags Dashboard Admin page, it just says "Loading..." and the video doesn't actually load. On the other install I have, same server, it does load a video.
Videos were working just 2 days ago. I haven't done anything since except upgrade to 3.3.2.
Problem solved: It is incompatible with the Use Google Libraries plugin. Once I deactivated this one, the video quicktags were working.