Package feed returned 401 Unauthorised, check the username and password for this feed. Also attempt to connect using NuGet.exe

We are currently having an issue with connecting the Octopus Deploy to the VSTS external feeds.
The following error is shown

Package feed returned 401 Unauthorised, check the username and password for this feed. Also attempt to connect using NuGet.exe.
HIDE FULL EXCEPTION
Octopus v2018.7.9

Package feed returned 401 Unauthorised, check the username and password for this feed. Also attempt to connect using NuGet.exe.
System.Exception
at Octopus.Core.Packages.NuGet.ExternalHttpNuGetPackageFeed.SearchForPackagesNamedLike(String packageId, Int32 take, CancellationToken cancellationToken, Boolean exactPackageIdMatch)
at Octopus.Core.Packages.NuGet.ExternalHttpNuGetPackageFeed.SearchPackages(String term, CancellationToken cancellationToken, Int32& total, Int32 skip, Int32 take)
at Octopus.Server.Web.Api.Actions.PackageSearchAction.ExecuteRegistered()
at Octopus.Server.Web.Infrastructure.Api.Responder1.Respond(TDescriptor options, NancyContext context) at System.Dynamic.UpdateDelegates.UpdateAndExecute3[T0,T1,T2,TRet](CallSite site, T0 arg0, T1 arg1, T2 arg2) at CallSite.Target(Closure , CallSite , Object , Object , NancyContext ) at Octopus.Server.Web.Infrastructure.OctopusNancyModule.<>c__DisplayClass14_0.<get_Routes>b__1(Object x) at CallSite.Target(Closure , CallSite , Func2 , Object )

We have tried with know working credentials and if we try to access the URL for the feed direct from the Octopus server it prompts for login and works but the application doesn’t seem to connect. I have upgraded the tentacles and the Application is at the latest version.