What iTunes told you is, bizarrely, correct.
If you think about it, it does kinda make sense.
When you implement a 301 redirect, you're essentially telling services like iTunes that the old feed URL isn't valid anymore, go look in the new location. So, iTunes does that and finds the new feed, bypassing the old feed where the iTunes New Feed tag exists. If the iTunes New Feed tag isn't also present in the new feed, iTunes may not realize what to do. Since the URL in the iTunes New Feed tag would match the actual URL of the new feed (when the tag is present in the new feed [I feel like I've opened some kinda interdimensional wormhole here]), there's really no harm in having it in the new feed.
I know you're hosting the new feed with Omny, so you'd need to check with them to see if they can add the New Feed tag to your new feed.