Can you provide some information about about the farm that you are backing up? Number and size of content databases, number of WFE, etc. Is the farm in a DMZ?
Also, please provide information about your backup plan such as your restore granularity options, number of content databases, WFEs, being included in the backup plan.
Please make sure that the SMSP service account has farm administration rights, local administation rights on the WFE servers, and that that service account has a sysadmin role in SQL.
You can take a look at the SMSQL backup report to see if the backups are actually completing.
Finally, what are you considering a "very long time" with 0% backup?
Thanks,
Mark