If you read this, it's probably because all the previous answers didn't work for your Holo Dark based theme.
Holo Dark uses an additional wrapper for the PopupMenus, so after doing what Jonik suggested you have to add the following style to your 'xml' file:
<style name="PopupWrapper" parent="@android:style/Theme.Holo">
<item name="android:popupMenuStyle">@style/YourPopupMenu</item>
</style>
Then reference it in your theme block:
<style name="Your.cool.Theme" parent="@android:style/Theme.Holo">
.
.
.
<item name="android:actionBarWidgetTheme">@style/PopupWrapper</item>
</style>
That's it!