Wow - that stinks. Expedia is totally dodging their responsibility.
Question - did you receive any kind of flight change notification from Expedia? I believe when you booked through them, they are supposed to send you flight schedule change updates. It sounds like they didn't send that to you, since you did not know about the Bulgarian Air segment. I would ask for compensation from Expedia on the basis that they did not advise you of schedule changes. They will probably try to get around this by saying that it's a passenger's responsibility to verify flight times, but it's worth a shot.
Second question - did you use any portion of the original business class ticket? If not, that is fully refundable, and Expedia should be refunding it since they issued it. That doesn't solve the problem of compensation, but it gets you some money back.
Thirdly (and I'm not 100% sure about this point, but someone else can chime in if I'm incorrect), when the airline changes for a ticket, the new airline can request paper tickets since they can't check you in on an e ticket from a different carrier. So Bulgarian Air was correct in requesting a paper ticket from you. Czech airlines should have been able to print your coupons at the airport or reissue the ticket, but it sounds like that didn't happen.
In any case, in my mind, Expedia has some responsibility to you to inform you that because of the airline change, you would not be able to use your original e ticket, and additional action was required.
hope that helps - good luck!