I was wrong in my previous post when I stated that it was a problem with the mySql version... I ran into the problem again on a new test server. I'll bet you money that the OOS lockdown tool modified folder permissions. You need to make sure that the IUSR account has read/list/write/modify access to the following directories:
cache
templates_c
uploads
That was my problem - somehow, the IUSR account did not have modify rights to the uploads directory and once I made the change, no more media upload errors which makes sense when you stop & think about it.