This server was already Apache (It was created as apache originally). I switched to nginx and permalinks started working. Switched back to Apache and they keep working… I guess the switch did the trick!!
Just out of curiosity, if you create a multisite server, with Apache from the start, can you replicate my issue?
Thanks!