Recipients can't open Excel

When I receive an Excel attachement that I work on, I save it as a "Microsoft Excel Workbook". When I forward it as an attachment in an email (Windows friendly attachment box and "attach file name" boxes checked), the recipient says he can't read it as it shows up as an unrecognizable file. The original Excel file was created on a PC and the recipient is a PC user. Should I be saving it as something else (MS Workbook x.x, MS Worksheet x.x, etc.) as the drop down menu has many choices or is there something else I need to do?

It might depend on the version of Excel the recipient has. Since I cannot explain what's causing this, I only have a suggestion that I'd call the "brute force" method. Try this if you want....

Open the file and do a SaveAs, but this time change the name of the file to what you're saving it as, such as "MS Workbook x.x"
Open the same file and repeat, using a different format.
Now send a batch of these "format named" files, and see if the recipient can open any of them, save it, and send it back to you. Return the favor. If it works both ways, now you know which format to use.

Is that impractical due to the sheer number of choices? If not, give it a go!