I assume that the recorder is greyed out all of the time and not for a specific workbook.

I wonder if some required installation options were unchecked when you installed Office 2013? I'd be surprised if this is the case because you said that the macro recorder is OK in MS Word 2013, but it's still worth a look. Re-insert the installation disc, choose Add or Remove Features and ensure that Visual Basic for Applications and Digital Certificate for VBA projects under the Office Shared Features are installed.