I turned off Sync Collections and Sync Bookmarks and Notes settings of iBooks (These were the only settings I could find about syncing) and then deleted and re-downloaded a book that I have purchased from iBooks Store.
Unfortunately, that did not bring back the New badge.