Over in Ronald's blog he has a good trouble shooting list for when your callout does not work.
He has missed one thing out though that still affects one of my sites.
In it the callout did not fire because the entity was updated by a workflow. Someone changed a bit value to indicate they had checked the record, the record had a status on a dropdown updated and that update should have then triggered a web service call to inform a third party of its existence and passage through a QA procedure.
After some experiments we discovered that if you changed the status of the dropdown by hand and saved it the callout was fired but if we allowed the workflow to change it then it did not. On googling MSDN this turned out to be a known issue pre rollup 1 but my client was only a week from go-live when we (I) discovered this. They have still not got around to applying the roll up as far as I am aware and the workflow was altered to create a task against an admin person to change the status by hand.
Not pretty but worth knowing.