I have found a solution myself but I want to share in case somebody is experiencing the same issue.
Here is what I have done:
Edited /etc/apt/sources.list.d/graylog.list:
commented out the old entry and added this one:
deb [trusted=yes] https://packages.graylog2.org/repo/debian/ stable 4.0
Removed the old version:
dpkg -r graylog-server
Updated:
apt-get update && apt-get clean
Confirmed that apt could see the new version:
apt-cache policy graylog-server
Installed without any further issues:
apt install graylog-server
All working fine after that!