The format produced by Spreadsheet::WriteExcel is the one used by older versions of Excel. As you've found, it has the limitations of the older version of Excel. Therefore you need to use a newer format.

The simplest option is csv. If this will not work (formatting is the usual reason why it won't) then you can step things up by creating an HTML file with a single table. Excel will load this without difficulty and you can do some formatting, but you will not have access to more advanced features of Excel. If you want that, Excel now saves files internally as XML in a zipped file. Nothing in principle stops you from creating the same exact XML.

If you wish to go this direction I would advise creating an Excel spreadsheet that looks like what you want it to look like and has all of the features you want. Unzip it. Then open it up and see if you can find where the stuff that is important for the data is. Then dynamically write that part, leave alone anything you can, and zip it up again. Then pray and try opening your file in Excel.

If you're really brave you could go to http://technet.microsoft.com/en-us/library/cc179190.aspx and try to figure out the format from the documentation that Microsoft provides.