Apple has changed the requirements of OSX’s internal file protocol (AFP) to version 3.3. Any external drive that wishes to take advantage of the Time Machine software must comply with this new requirement. WD’s internal software (on some NAS devices) does not yet meet this requirement, and as such, Time Machine on OSX 10.7.x (Lion) will not be able to establish a connection.

This was a real frustration for me having just bought a new Western Digital Elements 2 TB External Desktop Hard Drive, however fortunately there is a way around this. If you run the script found here you should be able to run Time Machine successfully. Took me a couple of days to find this so hope it helps someone.

Note: This also works on 10.7.3