And his federal colleague, Warren Truss, will be Acting Prime Minister when Tony Abbott, along with other world leaders, travel to South Africa to attend tomorrow's service for Nelson Man-dela. (ABC.net.au)
Why isn’t there number agreement between Tony Abbott and travel?
The notional subject is "Tony Abbott, along with other world leaders". The verb is agreeing with these words, not with the grammatical subject "Tony Abbott".
Strictly speaking, the verb should agree with the grammatical subject "Tony Abbott", since along with isn't a coordinator:
And his federal colleague, Warren Truss, will be Acting Prime Minister when [ Tony Abbott ], along with other world leaders, travels to South Africa to attend tomorrow's service for Nelson Mandela.
If you replaced along with with and, it would usually take plural agreement:
And his federal colleague, Warren Truss, will be Acting Prime Minister when [ Tony Abbott and other world leaders ] travel to South Africa to attend tomorrow's service for Nelson Mandela.
But notional agreement sometimes appears in cases like these, even in edited prose.