Y'know... I think I've actually found it! (With help from lord Google)
As soon as you reach 498 days uptime in Nagios, it resets and starts counting from 0 days again.
We have a router with an uptime of 2 years, 23 weeks
2*365 = 730
23*7 = 161
730 + 161 = 891 days
Nagios only counts to 498, and from this point starts counting from 0 again.
891-498 = 393 days
So in Nagios you would see 393 days of uptime, simply because it resets.
I've checked this on a few routers now, and in a way Nagios is actually correct.
Too bad tho that it does give a warning in the first hour of starting over again.
Now I'm curious if there is a solution to prevent this