Q: Can't I run icloud without having Lion or when tethering?

You need Lion or Mountain Lion (preferred) to be able to make use of iCloud for syncing your calendars, contacts and so on. I wouldn't have thought that using a tethered connection would have made any difference unless the service provider in question has some sort of limitation affecting it.