Photoshop Elements doesn't support CMYK, that's why it wants to convert to RGB when you try to opena CMYK file.
Usually, converting to CMYK is quite straight forward and easily done with Photoshop (full version). The only thing you need to setup is what target profile you want to use. Important: do NOT use any SWOP profile, it's intended for newspaper printing and colors and levels will be quite off when printed on normal paper. If you're converting through the site you linked to, make sure to use 'ISO Coated v2 300% ECI' instead.
There are some alternatives to Photoshop that support CMYK but if you don't want to dive into it, send me the files, I can convert them for you, no problem. Only thing is, I'll not be able to do it in the next 2 or 3 weeks (off for xmas).
Hope this helps!