I finally found out what was causing the problem:
Android library projects have to be added via the Android tab in the Project settings, not via the Java Build path. So, for adding the ActionbarSherlock dependency you have to open the settings of the HoloEverywhere project, choose the "Android" tab, click add and choose the ActionBarSherlock project.
I hope this helps future readers.