Laravel 5.1 on AWS - 500 error

I am trying to install Laravel 5.1 on AWS ec2 but with no luck. I chose the instance Ubuntu Server 14.04 LTS (HVM), SSD Volume Typewhen setting up but it seems as it is making many problems.

I was getting a 500 error with my current project, and even with a fresh laravel installation using composer. After turning error_reporting on and debugging it seems as the routes are working fine but the index.php is causing the following error:

( ! ) Fatal error: Call to a member function enableHttpMethodParameterOverride() on a non-object in /var/www/laravel/vendor/laravel/framework/src/Illuminate/Foundation/Http/Kernel.php on line 85
Call Stack
#   Time    Memory  Function    Location
1   0.0005  234848  {main}( )   .../index.php:0
2   0.0084  1678776 Illuminate\Foundation\Http\Kernel->handle( )    .../index.php:56

The PHP version that is installed is 5.5.28 which unfortunately does not meet the requirements of 5.5.9. However I could not find a way to upgrade to 5.6.x.

Googling and reading dozens of articles did not help as I could not find what is the correct ec2 instance I need to install and whether AWS actually support php 5.6.x. All upgrade guides failed.

My questions are:

1. Is anyone familiar with this error message. Is it actually related to php version < requirements?
2. Is there a way I could keep my current instance and simply upgrade php to 5.6.x?
3. If not, is there a recommended instance for Laravel 5.1 installation?

This is my first time using AWS and I am also not a ubuntu/unix expert so any help would be appreciated.

Thank you for your time.