Thank you for the replies, so what other reason would cause a transaction with which I believe to be proper fees to have a Medium priority transaction on the blockchain unlike the high priority which it usually is ?
Who says it has medium priority? If it's blockchain.info, keep in mind that they are notoriously bad at estimating when a transaction will be confirmed.
Besides an insufficient fee, another common reason for a transaction not being confirmed is an unconfirmed parent, i.e. when the transaction's inputs are not all confirmed.