Jason,
I've used my XA for about six years now and carry it with me everyday. I recently picked up a nicely working XA2 for my wife (she can't see the rangefinder patch in the XA). The point, that I'm slowly getting to here, is that the rewind knob assembly looks exactly the same in both cameras.
I've never used Fuji Costco film, but, being rebadged has got to be the only difference between that and other brands of film, right? Fuji Superia 400, Ilford XP2 and Kodak B&W are the only films I've ever used with my XA and have never had a problem, but, I will say that rewinding film is not as smooth as with any of my SLRs.
If it's any consolation, it looks to be a very easy repair if you can find another non-working XA-series camera with a working rewind lever. Ebay may be a good source for that, or, e-mail a camera repair shop and ask if they have the parts you need. There is also an Olympus XA website where you may find help for parts:
http://www.diaxa.com/xa/xastart.htm .
When you get your XAs repaired, I would first run a practice roll of film through them. Run the film through to the end and rewind with the back open and your thumb on the film cartridge to keep it in place. Then do it again with the back closed. If everything seems okay,...then fire away with some good film!
For what it's worth, I have one photo in my gallery taken with my trusty XA. It was taken at a Detroit Tigers game at Comerica Park (should be named Tiger Stadium!).
Good luck with both your XAs!
Marc