Matt,
I had a similar problem come up in the past. Unfortunately, it seems that these types of problems plague Belkin Wemo users. I tired everything you did and restored every device to factory settings. I uninstalled and reinstalled the Wemo, etc. Nothing seemed to work. The only workaround I have found is to set a rule to turn the light switch off. This was also Belkin's Support answer. It's just a fix for a symptom though, and not solition to the problem.
If you ever find a solution, please let me know!!!!