The Australian media coverage indicates that the problem was with checkpoint security in MEX, not with US customs in NY:
http://www.smh.com.au/travel/travel-...919-1kgxb.html
Originally Posted by SMH
Foreign Minister Kevin Rudd needed all his powers of diplomacy when his jar of Vegemite was almost confiscated by airport security at the weekend.
... The Mexican Foreign Service ensured Mr Rudd was able to get his Vegemite onto the plane...
Either he
also ran into problems with US customs on arrival, or WaPo have got the wrong end of the story. (Maybe both...) Note his actual tweet said he needed "Foreign Ministerial intervention". Last I checked, the US doesn't have "Foreign Ministers" and while Rudd is not my favorite politician, he's not stupid. I'm guessing WaPo assumed "at the airport" meant the US rather than Mexico.
But in answer to the OP's question: it was because of who he was. As noted, Vegemite has roughly the same consistency as peanut butter (that is, emphatically NOT a liquid) and is just as dangerous to air travel (that is, not at all.)