ERROR; Permission denied (13)

Hi there!
We have the CMS installed at a client's place, and recently moved the hosting.

Now when we want to login to the admin panel, it produces the following error:
Warning: session_start(): open(/var/lib/php/session/sess_nd89cba1lgep8pjf81pqhmrsb4, O_RDWR) failed:
Permission denied (13) in /var/www/vhostshttpdocs/cmsAdmin/lib/init.php on line 396
Couldn't start session! 'session_start(): open(/var/lib/php/session/sess_nd89cba1lgep8pjf81pqhmrsb4, O_RDWR) failed:
Permission denied (13)'! Warning: Unknown: open(/var/lib/php/session/sess_nd89cba1lgep8pjf81pqhmrsb4, O_RDWR) failed:
Permission denied (13) in Unknown on line 0 Warning: Unknown:
Failed to write session data (files). Please verify that the current setting of session.save_path
is correct (/var/lib/php/session) in Unknown on line 0

Now, I have searched this forum before, and the common answer to this problem was that sessions could not be created because of the lack of privileges. I tested this with a small php test script, with only:
<? session_start(); ?>
And this succeed, no error whatsoever.

So now my question, do you have a solution for this problem?
Sincerely,
Maurice

TL;DR: Permission denied(13) error, tried session_start(), that worked. All information is still accessible, just can't login.