O ActionBar tradicional evolui para a utilização do Toolbar, que é muito mais flexível. Recomendo que você utilize os princípios do Material Design e faça uso do Toolbar, assim você poderá alterar seu estilo de diversas maneiras, afinal ele é somente um View.
<android.support.v7.widget.Toolbar
android:layout_width="match_parent"
android:layout_height="?attr/actionBarSize"
android:id="@+id/toolbar_sort"
android:title="Toolbar"
app:popupTheme="@style/ThemeOverlay.AppCompat.Light"
android:background="@color/theme_primary_dark" />
Para definir o Toolbar como ActionBar
setSupportActionBar(toolbar);
Não esqueça de acrescentar em dependencies do graddle
compile "com.android.support:appcompat-v7:22.2.1"
EDIT: No eclipse você pode seguir estes passos para incluir a libs
EDIT 2: Não mencionei aqui, mas você deve alterar seu Tema, removendo o ActionBar para poder utilizar o toolbar como ActionBar corretamente.
<style name="Theme.MyTheme.Base" parent="Theme.AppCompat.Light.NoActionBar">
<item name="actionBarStyle">@style/MyActionBarStyle</item>
<item name="colorPrimary">@color/theme_primary</item>
<item name="colorPrimaryDark">@color/theme_primary_dark</item>
<item name="colorAccent">@color/theme_accent</item>
</style>
<style name="MyActionBarStyle" parent="Theme.AppCompat.Light.DarkActionBar">
<item name="android:background">@color/theme_primary_dark</item>
</style>