I decided to add a second answer to ensure that this is seen. I happened to try the same thing today using Windows Server 2003 and ended up reading the help in Windows 7. Something usefull we always ignore because google is so much quicker.
To add a location to the library it needs to be indexed. According to the help if the file is on a network location already indexed, it should be added without a hassle, however it does not define what would make the location appear as indexed.
The alternative method is to make the folder available offline. This can be done by right-clicking on the folder and then selecting Always available offline. The drawback is that the files will be stored on the local computer.
The latter defeats the object.
If your running 32Bit Vista or Windows XP and Win 7 you can install this add-in which allow the indexer to index network and UNC locations, however it is not available for 64Bit.
Another option according to this forum post is to create a symbolic link to the network share.