Previously we could delete our Zune and/or Windows Media Player databases in their respective directories and force a fresh interrogation.

Where are these files held for the new Music + Videos modern app in Windows 8? I'd like to force a new re-load?

Navigate to the following location and clear the contents of the folder

Appdata is a hidden folder.
Follow the steps given here to unhide the Appdata folder.
a. Press Windows Key + W Key, type: Hidden
b. Click Settings below the search box.
c. Click Show Hidden Files and Folders and drives on the left side of your screen.
d. Then click Show hidden files, folders, and drives.
e. Click OK

For clearing the Music Library

C:\Users\USERNAME\AppData\Local\Packages\Microsoft.ZuneMusic_8wekyb3d8bbwe\LocalState\Database

For clearing the Video Library

C:\Users\USERNAME\AppData\Local\Packages\Microsoft.ZuneVideo_8wekyb3d8bbwe\LocalState\Database

Note: “C” is the drive where your Operating System has been installed