Getting Remote Desktop sharing to work on Ubuntu is a real pain. It looks like it has something to do with the screen sharing service starting up before the user has logged in and having the keyring being still locked.
Changing from having my user automatically login to using a TimedLogin atleast allow for me to access the desktop over VNC and RDP.
Edit the Gnome Desktop config file:
sudo nano /etc/gdm3/custom.conf
And uncomment the TimedLogin block of code:
# GDM configuration storage
# See /usr/share/gdm/gdm.schemas for a list of available options.
# Uncomment the line below to force the login screen to use Xorg
# Enabling automatic login
# Enabling timed login
TimedLoginEnable = true
TimedLogin = luke
TimedLoginDelay = 10