If I set new bookmarks when I'm at work, the changes don't propagate to my iOS devices (which are also with me at work) or to my iMac at home. But if I set new bookmarks at home, they do propagate to my other devices, at least most of the time. I've noticed that sometimes new bookmarks set on my iPhone 5 or iPad 3 don't always propagate to my iMac or to my MBA. But my question is, could my workplace's overzealous (security security!) IT have something in place that interferes with iCloud syncing?
From this Apple Support document detailing TCP and UDP ports used by Apple software, iCloud uses these ports:
25 - smtp 80 - http 443 - SSL (HTTPS) 587 - Authenticated smtp 993 - SSL IMAP 5223 - DAV services
My guess is that it would be port 5223 which being blocked by your company.
As for your company's IT being 'overzealous', they are only doing exemplary due diligence protecting their network and server infrastructure, as well as any user (you) who connects, from nasties out there who would cause harm.