There are a number of ways to fix this.
Easiest way would be to start over with a new library and do a reimport from the network drive.
Another way is to enable Auto-import on the network device and change Fix Broken Links to yes.
http://wiki.jriver.com/index.php/Fix_Broken_LinksYou will want to switch it back afterwards so your files on the network are not removed from the library if your server goes down.
Another way is to use a smartlist to filter by file location and find all entries that point to your old drive (i.e File Location>E:\) and do a bulk remove from library.
Another way is to create a smartlist with all missing files displayed, [=ismissing([filename])]=1, and do a bulk remove, but this will be slow.
There are other possibilities as well.
What likely happened is that your library was not "new" like you thought or you didn't run a clear library before you moved your files. It is also possible that you did clear the library but had autoimport set up for your external drive while it was still connected to your computer (before you moved it). It's also possible that the library was not cleared and you could have easily pointed the database entries to the new network location by using the Rename, Move, and Copy Files tool and Updated the Database to point to your new network location by using the find and replace tool. This would have preserved your metadata and artwork.
http://wiki.jriver.com/index.php/Moving_FilesIf the above options don't work an easy solution would be to map your network share to the same drive letter as your external drive was issued previously. Then just do a library restore from an old backup.