Alright. So, I finally got it to work.
I used the Android BitcoinZ Wallet.
“Import Wallet” Does NOT work, at least it did not for me.
What did work was “New personal wallet”, then under “Show advanced options” you can change “Wallet key” to “Specify Recovery Phrase…”, which lets you set your own recovery phrase for your new wallet.
Here you set the recovery phrase that you have saved from earlier.
After the wallet was created using my recovery phrase it was still showing up empty, so what I then did was to go into “Settings”, choose my newly created wallet, go into “More Options” into “Transaction History” and “Clear Cache”.
I guess after that it forces the app to re-sync with Blockchain or something. I had to wait for maybe 10 more minutes and voila.
Anyways, in the end all my funds finally showed up inside that newly created wallet and I can access them now.
Hopefully this will help anyone reading this in the future.