Android Auto NOT WORKING With HTC ONE E9+?

[Legendpla]

Hey guys
I have a Pioneer AVH-X8750BT which supports Android Auto.
I also have a HTC One E9 Plus which is running Android 5.0.2 - which also supports Android Auto.

When I connect the phone to the Pioneer head unit, it starts the initial install process of downloading the app to my phone and making me agree to some ToS stuff which I accept, and then it (my phone) sits on a screen saying Android Auto. The Pioneer head unit however sits on a black screen with writing that says something like "cannot connect to Android auto, check your phone when it is safe".

During the entire process the car is parked with the handbrake applied - so it has nothing to do with that.

The strange thing is though, that it works with my dads HTC M8 perfectly fine, so it has to be an issue with my HTC ONE E9.

Does anyone have any information that might be able to help me? It just sucks having spent all that money on a new stereo and phone that supports Android Auto only to find that my new phone for some reason doesn't work.

Any more information can be provided if need be.

Thanks