I found my issue, it was related to the "Output Type" in the project configuration.
There are 3 choices in that drop down list : "Windows Application", "Console Application", and "Class Library".
If you don't select "Console Application", the service will not start. The reason for that is because you cannot set the Console Name if it's not a console application.
It may be easy to understand when you see it like that, but the errors were not very clear and easy to debug in Visual Studio.
So if you have the same issue, please make sure you select the output type "Console Application" on your project.