After spending a considerable amount of time trying all the options, the only way I was able to get an app using AppCompat v7 to change the overflow menu background was using the itemBackground attribute:
<style name="AppTheme" parent="Theme.AppCompat.Light.DarkActionBar">
...
<item name="android:itemBackground">@color/overflow_background</item>
...
</style>
Tested from API 4.2 to 5.0.