First of all, forget them not being able to work on the site. It's going to be hard for you to communicate with them and tell them what you want if they don't speak English (unless you speak their language).
Second, that depends on what you want them to do. If you just want them to touch up your sites HTML, then them not knowing English shouldn't be that big of a problem. However, there are lots of other jobs that a SEO company performs, like:
- contacting other websites and asking for links, most of which should be English speaking.
- determining what keywords you are going to target, and most of the keyword are going to be English words.
- writing SEO optimized content, which will require them to speak English.
So, basically, it depends on what you want them to do.