$ uprecords 
     #               Uptime | System                                     Boot up
----------------------------+---------------------------------------------------
     1   395 days, 03:45:56 | Linux 2.6.32-5-686        Sun Mar 22 22:49:29 2015
     2   329 days, 00:20:22 | Linux 3.2.0-4-486         Thu Apr 21 03:51:44 2016
     3   302 days, 10:01:37 | Linux 2.6.32-5-686        Sat May 24 13:25:38 2014
     4   176 days, 23:05:57 | Linux 2.6.32-5-686        Sun Oct 13 14:09:44 2013
->   5   162 days, 20:11:43 | Linux 3.2.0-4-486         Sun Apr 30 14:48:11 2017
     6   162 days, 20:07:45 | Linux 3.2.0-4-486         Sun Apr 30 14:48:10 2017
     7    81 days, 19:16:13 | Linux 2.6.32-5-686        Tue Jul 23 18:48:10 2013
     8    48 days, 23:31:15 | Linux 2.6.32-5-686        Tue Jun  4 18:42:47 2013
     9    45 days, 18:30:40 | Linux 2.6.32-5-686        Tue Apr  8 18:40:03 2014
    10    45 days, 10:15:11 | Linux 3.2.0-4-486         Thu Mar 16 04:32:43 2017
----------------------------+---------------------------------------------------
1up in    14 days, 02:54:15 | at                        Tue Oct 24 13:54:08 2017
no1 in   232 days, 07:34:14 | at                        Wed May 30 18:34:07 2018
    up   1751 days, 05:06:3 | since                     Tue Jun  4 18:42:47 2013
  down   -162 days, -12:-49 | since                     Tue Jun  4 18:42:47 2013
   %up              110.231 | since                     Tue Jun  4 18:42:47 2013
Negative downtime is awsome, huh?
This is because the bootid value can change sometimes, because ntp or something.

Anyway, I wrote this little workaround:
#!/bin/sh
NEW_BTIME=$(grep btime /proc/stat | cut '-d ' -f 2)
OLD_BTIME=$(cat /var/spool/uptimed/bootid)

if test "$OLD_BTIME" != "$NEW_BTIME"; then
  echo "New btime is: $NEW_BTIME"
  echo "Old btime is: $OLD_BTIME"
  service uptimed stop && echo "$NEW_BTIME" > /var/spool/uptimed/bootid &&
  cp /var/spool/uptimed/records /var/spool/uptimed/records.bak &&
  grep -v ":$OLD_BTIME:" /var/spool/uptimed/records.bak > /var/spool/uptimed/records &&
  grep -v ":$OLD_BTIME:" /var/spool/uptimed/records.bak > /var/spool/uptimed/records.old
  service uptimed start
fi
$ sudo ./uptimed-workaround.sh 
New btime is: 1493556491
Old btime is: 1493556490
Stopping uptime daemon: uptimed.
Starting uptime daemon: uptimed.
$ uprecords 
     #               Uptime | System                                     Boot up
----------------------------+---------------------------------------------------
     1   395 days, 03:45:56 | Linux 2.6.32-5-686        Sun Mar 22 22:49:29 2015
     2   329 days, 00:20:22 | Linux 3.2.0-4-486         Thu Apr 21 03:51:44 2016
     3   302 days, 10:01:37 | Linux 2.6.32-5-686        Sat May 24 13:25:38 2014
     4   176 days, 23:05:57 | Linux 2.6.32-5-686        Sun Oct 13 14:09:44 2013
->   5   162 days, 20:15:55 | Linux 3.2.0-4-486         Sun Apr 30 14:48:11 2017
     6    81 days, 19:16:13 | Linux 2.6.32-5-686        Tue Jul 23 18:48:10 2013
     7    48 days, 23:31:15 | Linux 2.6.32-5-686        Tue Jun  4 18:42:47 2013
     8    45 days, 18:30:40 | Linux 2.6.32-5-686        Tue Apr  8 18:40:03 2014
     9    45 days, 10:15:11 | Linux 3.2.0-4-486         Thu Mar 16 04:32:43 2017
----------------------------+---------------------------------------------------
1up in    14 days, 02:50:03 | at                        Tue Oct 24 13:54:08 2017
no1 in   232 days, 07:30:02 | at                        Wed May 30 18:34:07 2018
    up   1588 days, 09:03:0 | since                     Tue Jun  4 18:42:47 2013
  down     0 days, 07:18:13 | since                     Tue Jun  4 18:42:47 2013
   %up               99.981 | since                     Tue Jun  4 18:42:47 2013