Das Problem ist Behoben.
Der Fehler lag darin, dass folgende 2 Werte in der Konfiguration nicht gesetzt waren:
session.save_path
session.cookie_httponly
Nach dem setzen dieser 2 werte funktioniert session_start wieder.
Das OS war übrigens Linux 10 :D