The network center doesn't find a new wired connection when tethering is enabled.
Whether tethering is enabled or not, output of
lsusb | grep Samsung is same:
Bus 003 Device 009: ID 04e8:681d Samsung Electronics Co., Ltd Galaxy Portal/Spica Android Phone
Ubuntu 13.10 (updated), mobile phone: GT-S5830, Android 2.3.7 (CyanogenMod-7.2.0-cooper).
BTW, the phone doesn't automount as an Android Phone as well ("Disks" app shows SAMSUNG GT-S5830 Card (0100) as dev/sdb, but "No Media"). Works normally in the USB mass storage mode. A Galaxy SII on the same machine mounts/tethers with zero problems.