Altering database tables belonging to core modules Using D6's date_api.module module, I noticed that the .install uses db_add_field() to add a "timezone_name" column to the {users} table, and hook_schema_alter() to declare that change. 

I was surprised to see a module alter a core module's table, and would have instead expected date_api to create a {date_user_timezone_names} table with "uid" and "timezone_name" fields (and subsequently a hook_user($op='load') to add a timezone_name property to the user object).

The advantages of simply adding a column to another module's table are obvious to me. I'm interested in hearing what the disadvantages are. Are there any gotchas that one should be aware of?
Yes, I'm not sure altering core tables is a good idea.

I don't see any problem with it, as long as you just add fields. 

But I remember having seen some code here and there that cycles through all the fields in a table, so even this might cause problems.

It's a bit personal and question of belief, but as far as I can, I try to make my code as something that can work with core's code and structure. I've seen too many devs going in implementation hell with decisions like that.

Also, having to alter what's already been designed by big teams and/or big guys like core devs is very often due to a bad analysis of the use case.

My general advice for anybody who's lower than core dev level (including me, of course) would be : don't do it.