I'm working on refactoring a legacy application where I implemented the State pattern successfully as shown in the following diagram:

As you see there is a common behavior between the 3 states, so I decided to extract the common method Refund() to a parent abstract class RefundableState where I implemented it:

Refactoring further I notice that the Ship() method is common between the 2 states Cancelled and NewOrder, so I go for another round of extracting the common behavior to another parent class ShippableState:

Now I need my Cancelled state to extend 2 classes and in the same time I can't group the Refund() and Ship() function together as not all state permit the 2 actions.
How can I fix this?
Notes:
- This question is mainly about applying DRY and refactoring not about how to implement the state pattern.
- I'm using PHP 5.3, but I'm open to answers in any other languages.