What resolution are you trying to give them?
I'm guessing rather they're referring to the DPI. When you open a document in Photoshop (canvas), change the resolution to at least 300dpi. That's considered print quality. 72dpi, which is probably what you're using, is considered web quality.
Really for a logo, especially for printing, you should be using Illustrator and creating vector images.
Have you looked at the image I linked in my last post? You would do that when opening a new canvas to create an image.
If you already have an image, go to Image -> Image Size and then change the resolution in the box that comes up. It's probably defaulting to 72dpi.
Hmmmmm. That's a weird one. I'm not sure you want to use the "Save for Web" when you're doing higher-quality stuff. Try going to "Save As" instead, make sure the quality is set all the way up (12), and save it in a lossless format (TIFF, for example.).
It could very well just be their system too.