My motd persistently has:

*** /dev/sdb1 will be checked for errors at next reboot ***

The problem is that I don't have /dev/sdb1 on my system.

I only have /dev/sdb2 (mouted as /) and /dev/sda1 which mounts to /media/backup. I delete that line from /etc/motd, but it reappears after reboot. Here's my df output:

Filesystem      Size  Used Avail Use% Mounted on
/dev/sdb2        73G  3.7G   66G   6% /
udev            490M  4.0K  490M   1% /dev
tmpfs           200M  760K  199M   1% /run
none            5.0M     0  5.0M   0% /run/lock
none            498M     0  498M   0% /run/shm
/dev/sda1       1.9T  429G  1.4T  25% /media/backup

Update

Here is the output of sudo fdisk -l

Disk /dev/sda: 2000.4 GB, 2000398934016 bytes
255 heads, 63 sectors/track, 243201 cylinders, total 3907029168 sectors
Units = sectors of 1 * 512 = 512 bytes
Sector size (logical/physical): 512 bytes / 512 bytes
I/O size (minimum/optimal): 512 bytes / 512 bytes
Disk identifier: 0x0003dfc2

   Device Boot      Start         End      Blocks   Id  System
/dev/sda1              63  3907024064  1953512001   83  Linux

Disk /dev/sdb: 80.0 GB, 80026361856 bytes
255 heads, 63 sectors/track, 9729 cylinders, total 156301488 sectors
Units = sectors of 1 * 512 = 512 bytes
Sector size (logical/physical): 512 bytes / 512 bytes
I/O size (minimum/optimal): 512 bytes / 512 bytes
Disk identifier: 0x00049068

   Device Boot      Start         End      Blocks   Id  System
/dev/sdb1       152301568   156301311     1999872   82  Linux swap / Solaris
/dev/sdb2   *        2048   152301567    76149760   83  Linux

Partition table entries are not in disk order

I guess /dev/sdb1 is my swap space.

It does look like it might be a swap problem. Can you manually fsck the drives from single-user mode (e.g., by booting into recovery mode)?

You can do a sudo mv /var/run/motd /var/run/motd.old to force a clear of the current /etc/motd file.

Also, can you add output of your from cat /etc/fstab ?

For swap operations, see these answers:

delete old swap partition

How to delete a second swap partition safely?

A nice graphical swap repair guide using gparted is here.

Looking for help on the same issue, and the search that brought me here.

I came across this forum discussion Ubuntu Forums which posed the following command as solution:

sudo touch /forcefsck

I tried it and the message was cleared on next reboot. Some have commented that this does not always work, but I hope it helps you too.