Same issue here.
For me adding the connected apps (ios, android) to the profile was the solution.
In Lightning Experience:
Setup => Users => Profiles => --Select appropriate profile-- => Assigned Connected Apps => Edit.
Select "Salesforce for Android" & "Salesforce for iOS" and add to the right side pane then Save.
Make sure to set "Api Enabled" as well.
Setup => Users => Profiles => --Select appropriate profile-- => System Permissions => Edit => Tick "Api Enabled".
If Tabs are not displaying, ensure the associated VF pages are Lightning enabled (find page in setup by searching visualforce in settings quickfind and select appropriate page(s) then tick the checkbox for enable for lightning etc) and that they are assigned permissions to that profile as well. Visualforce Page Access is in the same profile permission page above. Select edit and move to the right pane.
Check the user record has Mobile User ticked as well.