Linux can't see any of my partitions — The backup GPT table is not at the end of the disk

I'm trying to install Linux on my HP Pavilion 14 inch ultrabook, but without any success.

At first I tried installing Ubuntu on it; everything went fine, I got into the Live DVD (yes I'm oldschool like that), and went to install the system on my disk. First weird thing that happened was that I wasn't prompted with the option to install Ubuntu alongside Windows, but instead got thrown directly into the window with the partition table. Or rather, lack thereof.

You see, the window showed my drive as being sda, but no partitions are visible. None. Not the one with windows on it, not any of the ones windows requires, not even the 500 GB free space on my drive that I made specifically for Ubuntu to play on. None of it.

I then went on to try and install Arch on my machine instead, hoping the more barebones system would be able to see my partitions. And indeed it did not. Exact same story as before, it can see the hard drive, but it cannot see any of the partitions.

This bugs me endlessly and I haven't been able to find any information about this on-line.

So what can I do? Is there some kind of trick to make the partition table visible? Everything else seems to be working, even the WLAN card (the one thing I always have trouble with) works. Any help?

NOTE: The ultrabook came with Windows 8

Screenshot of sudo fdisk -l as requested:

Trying to run parted gives me the following error:

Error: The backup GPT table is not at the end of the disk, as it should be.
This might mean that another operating system believes the disk is smaller.
Fix by moving the backup to the end (and removing the old backup)?

Following the suggestions below, I tried running sudo gdisk /dev/sda and got the following:

GPT fdisk (gdisk) version 0.8.8

Partition table scan:
  MBR: protective
  BSD: not present
  APM: not present
  GPT: present

Found valid GPT with protective MBR; using GPT.

What should I do here?