Validation Rule Help - Dependent Value

I need help with a validation rule. There is a custom field on a custom object called "Status" -- There is a status that is "In Progress" -- however that status can only be selected if the value of a different custom field "Subscription Product Status"  is either 1 of  2 different values. (Fulfillment or Live) I wrote this validation rule:  

OR(
AND (
    ISPICKVAL(Status__c,'Ad Fulfillment - Ad In Progress'),
    Subscription_Product_Status__c != 'Fulfillment'
       ),
AND (
     ISPICKVAL(Status__c,'Ad Fulfillment - Ad In Progress'),
        Subscription_Product_Status__c != 'Live'
        )
   )

Here is the problem though. If the value is "Live" then the first AND criteria blocks the record from being saved and if it's Fulfillment the second on blocks it. I've tried a bunch of different ways to solve this and I can't figure it out... this can't be that hard.