14.04 - Invalid partition table after windows removal

Originally, there was Windows 7 installed on a laptop that I was given by my employer to work on. I installed Ubuntu 15.04 next to Windows using bootable USB. Recently, I have received permission to delete Windows, so I used gparted and formatted the partition with Windows to ext4. Now, when I start the laptop, I get "Invalid partition table" message. After pressing any key, Ubuntu normally boots up and I can see no other problems.

Do you know how to deal with Invalid partition table error?

Edit#1

I made a mistake - it's Ubuntu 15.04, not 14.04. I tried installing boot-repair but it seems that there is none for Ubuntu 15.04.

The output of sudo gdisk -l /dev/sda:

GPT fdisk (gdisk) version 0.8.10

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



***************************************************************
Found invalid GPT and valid MBR; converting MBR to GPT format
in memory. 
***************************************************************

Disk /dev/sda: 500118192 sectors, 238.5 GiB
Logical sector size: 512 bytes
Disk identifier (GUID): 921B3CFE-5AE9-4D20-A006-8212D26F78EC
Partition table holds up to 128 entries

First usable sector is 34, last usable sector is 500118158
Partitions will be aligned on 2048-sector boundaries
Total free space is 5932 sectors (2.9 MiB)

Number  Start (sector)    End (sector)  Size       Code  Name
   1            2048       224854848   107.2 GiB   8300  Linux filesystem
   5       224856064       483569663   123.4 GiB   8300  Linux filesystem
   6       483571712       500117503   7.9 GiB     8200  Linux swap

Edit#2

I upgraded Ubuntu to 16.04 LTS and ran boot-repair, but it didn't help. The report can be found here: http://paste2.org/wGJCdmaZ.
Boot-repair also mentioned:

The boot files of [The OS now in use - Ubuntu 16.04 LTS] are far from the start of the disk. Your BIOS may not detect them. You may want to retry after creating a /boot partition (EXT4, >200MB, start of the disk). This can be performed via tools such as gParted. Then select this partition via the [Separate /boot partition:] option of [Boot Repair]. (https://help.ubuntu.com/community/BootPartition)

But as Ubuntu eventually boots up correctly, can it be a problem?