Ran into this the other day. “Connect to Outlook” was unavailable (greyed out/disabled) in a new SharePoint 2013 farm. Often you’d see this if you are using an unsupported browser in previous versions of SharePoint (Firefox, Chrome, etc. was an IE ‘only’ thang).
The quick solution in our case was to deactivate the “Minimal Download Strategy” site (web) feature and this returned the functionality immediately. The Minimal Download Strategy is a pretty cool new feature but won’t always be a fit and in this immediate case, disabling it was a working solution until we find the root cause. We suspect it may be a missing element in a custom master page and thus it doesn’t support MDS. More on that later. There are other issues out there on the interweb that suggest you need to decide if MDS works for you or not. This is at least quick and simple.