I solved this. Here's what I have:
Macbook pro early 2011, OSX 10.6
LS-QVL 4.0TB Linkstation Quad Pro
Steps:
1) Set up a time_machine (or some other name) directory on the NAS web GUI - when doing so, uncheck recycle bin, check Apple, check Disk Backup, uncheck windows (to be safe)
2) under Extensions->Time Machine on the NAS web GUI, click Modify Settings and choose the time_machine directory (created in 1)) and also click Enable in the Time Machine tab. In the MAC information tab, you'll need to fill in the computer name and the MAC address. Do the following to obtain those:
a) for the computer name, go to Spotlight and type the word "Sharing" - click the "Top Hit", which will bring you to the Preferences->Sharing window. Where it says "Computer Name", there's an Edit button. Click it, and notice that it already has highlighted a slightly-different version of your computer's name, sanitized for access over a network. Simply copy that precise name (WITHOUT the .local extension, which isn't highlighted anyway), and paste it into the "Target Host Name:" field in the MAC Information tab
b) for the MAC address, go back to the System Preferences window, and Click Show All and then click on Network. Whether or not you are connected to the NAS by Airport wireless or a wired connection through a switch etc., click on Ethernet in the left hand pane. Then click advanced at the bottom, and click on Ethernet within that window, then highlight and Copy the Ethernet ID to the clipboard. Paste that ID into the "Target MAC address:" field in the MAC Information tab of the NAS Web GUI. Now, there is some contention here on whether you should remove the ":"'s from the address before pressing "Create" at the bottom. My advice is that if you attempt to remove them, and the text box in which the ID has been pasted turns RED, then put the ":"'s back (making sure to have a colon every two characters). On the LS-QVL (where the text box turns red if ":"'s removed), the ":"'s needed to STAY. At this point, you should be ready to click "Create". NOW - AND HEAR THIS - *IF* clicking "Create" has been successful, then your MacBook will flash up an information Alert box telling you that it had "successfully created disk image" (or similar words). If so, then go and have a look in your time_machine directory in finder. You will see a sparsebundle file there which has the slightly-different version of your computer name at the beginning (the name sanitized for use on a network from part a)). For some reason, the time stamp on my sparsebundle was a bit screwed up, but I ignored this and it was fine.
NOW - You are probably reading this forum entry because you've already had problems with Error 45. As such, your time machine app on your MAC will be a little confused. You've clearly gone and told it that it should use the time_machine directory on the NAS for Time Machine backups, but it just couldn't make the sparsebundle for some reason. This time, however, I want you to go to your Time Machine button in the menu bar at the top of the Desktop, and click "Enter Time Machine". To check if you've had some success, go to Finder and see if "Time Machine" is now listed under your "Devices" in the left hand pane. If so, go back to your Time Machine menu above the Desktop, and click Backup Now. A few cobwebs might suddenly lift, and you'll find yourself backing up with the NAS - go get a piece of cake to celebrate (or maybe a flux capacitor)!
Good luck to everyone with ERROR 45. Please persevere, Time Machine DOES work with the Buffalo NAS, I just think Buffalo have been a little bit Lazy with writing up the FULL explanation. I don't work for Buffalo, I just looked around at some of the suggested fixes and used more than a fair bit of know-how to get it working for me. I hope you find this helpful!