My company is extremely international, and all business is done in english, so there is no problem. Other companies I interviewed with did bring it up as a problem. Startups seem to care very little, major corporations care a lot.
Immersion helps a lot for languages.
I've lived in Denmark for 2 1/2 years and probably have had less real need to speak Danish here than in the 3 weeks I spent in Spain! More Spaniards are either unable or unwilling to speak English, so that trip was much more immersive language-wise, in that I actually had to interact in Spanish.
My personal theory is that Spanish Spanish (i.e., from Spain) has a range of spoken sounds that is to a large part complimentary to that of English, thus making the transition between these two languages particularly difficult. (Note that there is significantly less of a difference between the sounds of American Spanish and English).