You're right. Further discussion in that bug and on twitter [1] confirm that Firefox is affected after a restart. The author of this didn't restart.
So any removal instructions which don't include clearing out Firefox's certificates are incomplete. This includes Lenovo's published instructions.
[1] https://twitter.com/FiloSottile/status/568600661534875648