Hi @grehce, welcome to the GitLab Community forum! 
I’ve seen other GitLab users have this problem before and believe I know what the solution is.
When “Private Token” is selected for “Auth Type” for connecting GitLab to Sourcetree, you actually need to enter a Personal Access Token in the “Password” field, not your regular password. Sorry for any confusion.
To generate a private token, navigate to https://gitlab.com/profile/personal_access_tokens, create an personal access token with scope of api, read user, and write repository, and use this in place of your password when connecting your account to Sourcetree.
For GitLab CE the steps to set up Sourcetree to use private token will be almost identical, the only difference being the URL to create the token to use in place of your password will use a different URL: <your_gitlab_url>/profile/personal_access_tokens
Please let us know if this resolves the problem for you, and don’t hesitate to ask if you have any questions.