linux - No space left on device, df shows 50%

I have done everything I know about, and now I'm completely lost.
I'm getting an error on my Storage partition. The drive is a ntfs, and I'm using ntfs-3g, the disk is being shared between my Windows and my Linux partitions.
But I don't think that any of that should be an issue though.

I started off with the obvious df -h

Filesystem      Size  Used Avail Use% Mounted on
/dev/sda3       772G  434G  339G  57% /media/Storage

The partition that is of interest is /dev/sda3 -- the partition labeled Storage.
It seems I'm only using 57%.

I then booted into my Windows partition and ran a chkdsk e: /r on the drive. It did find and correct some errors. However, it didn't fix the 'no space left on disk' error.

After some googling, I notice a lot of people with the same problem found a solution that deals with inodes, so I check that df -ih

Filesystem     Inodes IUsed IFree IUse% Mounted on
/dev/sda3        340M  414K  339M    1% /media/Storage

Seems /dev/sda3 is only using 1% of inodes, and according to @grawity. NTFS won't have problems with inodes since the space is dynamically allocated.

I ran a dmesg, but there doesn't seem to be anything obviously wrong, nothing that I can tell, but I'm not very familiar with the contents.
See the dmesg output at http://pastebin.com/jtrf8NB3

I was requested to look at ntfs-3g --version since apparently there used to be a bug where it would report 'no space left on device', but that was an older version.

ntfs-3g 2012.1.15AR.1 external FUSE 28

ntfs fragmentation does not seem to be the problem as it only had a 5% fragmentation. The partition was defragmented regardless.

As requested this is the output of a mount command:

/dev/sdb1 on / type ext4 (rw,errors=remount-ro)
proc on /proc type proc (rw,noexec,nosuid,nodev)
sysfs on /sys type sysfs (rw,noexec,nosuid,nodev)
none on /sys/fs/fuse/connections type fusectl (rw)
none on /sys/kernel/debug type debugfs (rw)
none on /sys/kernel/security type securityfs (rw)
udev on /dev type devtmpfs (rw,mode=0755)
devpts on /dev/pts type devpts (rw,noexec,nosuid,gid=5,mode=0620)
tmpfs on /run type tmpfs (rw,noexec,nosuid,size=10%,mode=0755)
none on /run/lock type tmpfs (rw,noexec,nosuid,nodev,size=5242880)

none on /run/shm type tmpfs (rw,nosuid,nodev)
/dev/sda2 on /media/Windows type fuseblk (rw,nosuid,nodev,allow_other,blksize=4096)
/dev/sda3 on /media/Storage type fuseblk (rw,nosuid,nodev,allow_other,blksize=4096)
/dev/sda5 on /media/Linux_partition type ext4 (rw)
binfmt_misc on /proc/sys/fs/binfmt_misc type binfmt_misc (rw,noexec,nosuid,nodev)
gvfs-fuse-daemon on /home/golden/.gvfs type fuse.gvfs-fuse-daemon (rw,nosuid,nodev,user=golden)