XML sitemap is garbled when I turn on cache

I get this as XML output for example:

"��������P�n�0����
��i,C�N��T��,qo�����R)�}���1��s���s�
��*��79�<�%�|W<�� �`@��=�`"9�����R��(j8��Ix ���e��B�5d3�����Eav���ab�����"�Ī�ʛ�[~�� �o\-�L�T~��?fb=R�+�,��"�UIKز�˼䋩k���0.T�F�1��3Ҹ)�Y�T�D���吭t����Y)�T�]!�Əv�o��Y���
��"

Without quotes of course, and this does NOT validate properly.

Here are my options set in admin/settings/performance

Caching mode: Normal
Aggregate and compress CSS files: Enabled