Remote off is key. Once a remote is paired with the locomotive, nothing else will work. This problem occurs with the phone app and also the orange universal Lionchief controller (available separately). Unfortunately, it sounds like you got that far and it still didn't work. Fortunately, you are still able to control the train via the remote.
I have had mixed results with the phone app on Android and it is very frustrating. Sometimes it works great, sometimes it can't find the locomotives. Try a different phone, or a tablet. I don't know what to tell you. Lionel is very wise to provide the remote with all their starter set engines, because the app certainly isn't reliable enough for general use.
For what it's worth, we tried the phone app and prefer the remote. Also worth nothing that with the old style trains where you controlled them via the transformer, there was no danger of misplacing the controller because it was hardwired to the layout.
