It does. Basically, if it resists the typing of any of her Pokemon (or hits any of them super-effectively), it can't be used against her.
This leaves me with a pure Normal type or Sudowoodo. Since only STAB moves can be used (another prior restriction) and Lucario 4x resists Rock, I can only use a pure Normal type for this. No Normal type available can solo Maylene without being grossly overleveled. I'm sorry, but I have to reject this unless you change it.
Unless Naix changes his challenge, I will accept one more post-Gardenia challenge!