Finally found a solution to the problem!
First of all the SoftwareSerial pins need to be on another PORT than the Pins for the Change Interrupt.
One has to modify the SoftwareSerial.cpp to exclude the PCINT vector that does cover the PORT that includes the pins to handle. You can do this in the library directory of you arduino install, but better is to put a copy of the file in your program dir and include it with parenthesis (<> will include the standart library).
So how to modify? First you need to know which Port of the ATmega your pins belong to.
A0, A1 | PC4,PC5 | PCINT12,13 | Interrupt vector 1 - PCINT[14:8]
D0 | PD6 | PCINT22 | Interrupt vector 2 - PCINT[23:16]
D1..5 | PB1..5 |PCINT1..5 | Interrupt vector 0 - PCINT[7:0]
then you can disable the ports in SoftwareSerial.cpp (line 227 ff.) (PCINT3_vect is for bigger chips).
You need to keep the first ISR(PCINT0_vect), because the other are only aliases of that. If you want to disable PCINT0_vect you need to rename the first ISR to PCINT1 and reference to that one from the other ISRs.
In PinChangeInt Library you can simply disable the port that is used in the softwareserial by adding a
#define NO_PORTx_PINCHANGES (where x is B,C or D) in before the library include.