The problem isn't the dependence upon the fee of the previous transaction, but rather that the OP used unconfirmed inputs in his transaction.  Yes, those inputs were unconfirmed because the fee was 0, but the OP further complicated the matter by using those inputs in his own transaction.

As DannyHamilton mentioned, unless a pool is using a look-ahead method to know that by confirming the unconfirmed inputs they will be receiving fees from the child transaction, OP is forced to wait for those inputs to confirm.  Since it appears the transactions finally confirmed, everything is good to go.