So⦠you decided to finally configure backup for your servers, and just when youāve chosen the ābackup solutionā, troubles start. 
What do we need for doing Windows Server backups?
Nothing too fancy ā we can use the built-in Windows Server Backup (feature that needs to be installed through Server Manager, PowerShell, ā¦) combined with some location (network share, disk, volume) with enough free space. (yes, we can also use some other backup software, but this is not the topic here)
Letās say that we have installed Windows Server Backup feature and chosen a network share for our backup location. The one other thing we need on this share are the right permissions for our service account (an account under which the backups will be done ā for example, BackupAccount).
So, we go to this share (\\BackupLocation\MyBackups\) and check if our service account has the required permissions:

Everything looks fine (our service account has permissions, folder is shared and accessible from the source server ā yes, Windows Firewall is also configured properly
).
We go back to our source server where we configure our backup schedule as a Full Computer backup, once a day, to the backup location previously mentioned, using the service account previously specified for this backup job. Everything goes fine.
Then, just for fun, we try to run our backup schedule (just to see if everything works as it should). We click on the Backup Once option (with Using the previously scheduled⦠option), and just at the end of this wizard, we receive the following error, saying that our backup destination is not writable (yes, itās the good old Windows Server 2008 R2, but it really doesnāt matter⦠the same happens on newer/older versions as well
):

What happened???
Weāve checked (and double-checked) everything ā our share, permissions, Windows Firewall, and āwho knows whatā, and this wizard still says we cannot write to the backup destination! This must be an issue with the free, out-of-the-box backup solution.
Not really.
The issue here is that Iām running the Windows Server Backup console as āmyselfā (i.e. my user, for example, SERVER\tomica) and I donāt really have the required permissions on the backup share (Iām not a member of the local Administrators group on the backup destination and, as you may remember, only our BackupAccount has the required permissions set).
So, is this an issue?
No, not really because our scheduled backup will complete successfully (it will be running under the user account with correct permissions on a backup share).
And, if we really want to make this first backup right now, we can run it from the Task Scheduler console (by checking the āAllow task to be run on demandā checkbox first, for the backup task).

Hope this helps someone with similar problems (itās kind of a dumb āissueā, butā¦). 
Cheers!