To fix my problem I added to the connection string Connect Timeout=1000;. After doing this I no longer receive the error message while the file is open.
However, this seems to leads to another problem. The Connect Timeout connection string parameter is not persisted. Immediately after I save the connection string, if I open it up again Connect Timeout=1000 is missing. This doesn't seem to be an issue
by itself because if I Refresh, it still seems to works. If I save and reopen the document it too seems to still work.
However when I save the spreadsheet under a new name, I get the error message again. Also if I change the connection string anywhere else I get the error message again.
I'm sorry I didn't post my query, but in Excel it's just [Model]. More over it is clear the problem is Excel 2016, and has nothing to with my cube that was running fine (albeit slowly) in Excel 2013.