Hi, I just recently had to deal with a issue simlar to yours in two very distinct environment; and basically the only couple of advice for you to troubleshoot your situation is as follows:
1. UNC PATH--> make you're using \\servername\backup_Folder)
2. SHARE--> make sure that the folder mention above is shared, and the "domain\application_pool", and "domain\ssp_service account for the farm or web application as: FULL Permision for both the SHARE and NTFS. There are many options of setting this up; however, the bottom line is getting this two accounts the neccessary rights.
PS: For kicks, you might want to give "EVERYONE" account in the share permission "FULL" control.
Good Luck.
Mohammed Onibudo