Is there some preference field or setting in the CP that might make the 'Show toolbar' link to disappear from the publish page? Mine has vanished for a particular custom member group (the only group that I'm using apart from Superadmins), although it shows up fine when I'm logged in as an SA. This made me think that it was something in the preference settings for that particular member group, but AFAICT nothing in that long settings list deals with the ability to customise publishing layouts.
Any ideas?