I have a MySQL 5.0.16 running on SuSE Linux 10.
When I connect to this MySQl from another machine running WinXP/SQLyog I can easily ALTER TABLE to varchar size greater than 255 (the upper limit before MySQL 5).
i think it is an issue with your MYSQL installation on LINUX. Did you update from a previous MySQl version? Did you then run the update scripts after updating.
I think you should try to dump your data, remove MySQL on LINUX (including deleting the /datadir), and then reinstall and import data.
I don't know the .deb install packages. it could be a problem here when upgrading. There is no such problems with the .rpm install packages used by RH/FC/SuSE.