MY NTFS Partition has gotten corrupt somehow (it's a relic from the days when I had Windows installed).

I'm putting the debug output of fdisk and blkid here.

At the same time, any OS is unable to mount my root partition, which is located next to my NTFS partition. I'm not sure if this has anything to do with it, though. I get the following error while trying to mount my root partition (sda5)

mount: wrong fs type, bad option, bad superblock on /dev/sda5,
       missing codepage or helper program, or other error
       In some cases useful info is found in syslog - try
       dmesg | tail  or so

ubuntu@ubuntu:~$ dmesg | tail
[ 1019.726530] Descriptor sense data with sense descriptors (in hex):
[ 1019.726533]         72 03 11 04 00 00 00 0c 00 0a 80 00 00 00 00 00 
[ 1019.726551]         1a 3e ed 92 
[ 1019.726558] sd 0:0:0:0: [sda]  Add. Sense: Unrecovered read error - auto reallocate failed
[ 1019.726568] sd 0:0:0:0: [sda] CDB: Read(10): 28 00 1a 3e ed 40 00 01 00 00
[ 1019.726584] end_request: I/O error, dev sda, sector 440331666
[ 1019.726602] JBD: Failed to read block at offset 462
[ 1019.726609] ata1: EH complete
[ 1019.726612] JBD: recovery failed
[ 1019.726617] EXT4-fs (sda5): error loading journal

When I open gparted (using live CD), I get an exclamation next to my NTFS drive which states

Is there a way to run chkdsk without using windows ?

My attempt to run fsck results in the following :

ubuntu@ubuntu:~$ sudo fsck /dev/sda
fsck from util-linux-ng 2.17.2
e2fsck 1.41.14 (22-Dec-2010)
fsck.ext2: Superblock invalid, trying backup blocks...
fsck.ext2: Bad magic number in super-block while trying to open /dev/sda

The superblock could not be read or does not describe a correct ext2
filesystem.  If the device is valid and it really contains an ext2
filesystem (and not swap or ufs or something else), then the superblock
is corrupt, and you might try running e2fsck with an alternate superblock:
    e2fsck -b 8193 <device>

Update : I was able to fix the NTFS partition running chkdsk off HBCD, but it seems that the superblock problem still remains.

*Update 2: * Fixed superblock issue using e2fsck -c /dev/sda5