FFMpeg and HLS, videos need to load in their entirety before they start playing
So it turns out after a lot of research that this is the desired behaviour for Apple's AVPlayer component. Basically, my Internet is so slow here where I live, the component waits until the video has fully downloaded before it starts playing. The best and recommended way around this, is to generate alternate streams for the video before trying to play it. Here is documentation on the m3u8 format and HLS streaming guidelines:

https://developer.apple.com/library/ios/documentation/networkinginternet/conceptual/streamingmediaguide/Introduction/Introduction.html

I followed the above and generated two extra streams from the original: a 200kbps, 400kbps, and playback now starts almost immediately. Your mileage may vary depending on the speed of your Internet connection.

Alternatively, if you don't have to use something like HLS, you can use plain mp4 files. Make sure that they have -faststart enabled if you are processing the file with ffmpeg.

Update: To simplify this for other developers, I have released an SDK that is able to upload your mov or mp4 files to a cloud service and convert the file to an HLS compatible stream. The SDK can be installed via Cocoapods and you can access documentation and the framework here: 

https://github.com/Storie/StorieCloudSDK