For anyone else who may run into the same issue, the problem was that I synced my Music after running my application. You need to observe for Library changes:
MPMediaLibraryDidChangeNotification
[[MPMediaLibrary defaultLibrary] beginGeneratingLibraryChangeNotifications];