(I may be wrong on some of the below as I havent followed it closely, but my understanding is something like this:)
Say for example Microsoft are allowed patent the structure of their .doc files for MS Word. Now, any company that want to use the file format has to get explicit permission from Microsoft, and quite possibly pay them a fee. So the next time (eg) Adobe release a new version of Acrobat featuring an export to/from Word feature, they have to pay a chunk of money to Microsoft, or not provide the feature and severely dent the market value of their product.
This is why the open source movement is really up in arms about it – Microsoft can simply completely refuse to allow and 3rd party software running on Linux (Star Office for example) to be allowed to read their Word files. Bye bye competitors, hello even easier market monopolies for Microsoft.
Obviously this is just one example, and Microsoft have already stated that they plan to use XML for forthcoming Office releases, but by making file contents proprietary to a single application, all market competition becomes much easier to extinguish.
The GIF issue was different not because of the file type, but because they received a patent for the algorithm used to generate the gif file. Thus, anyone using a gif file had to implement the patented algorithm. I’m not sure if I particularly agree with this either, but at least there is a distinct difference.