JudasIscariot: I am not sure if this applies to the first game as I've only played CKII so far :)
In any case, your previous ruler probably had a bonus to vassal opinion because of his long reign on top of any bribes and such. Powerful vassals will always try to rebel whenever there is a change of ruler so your first order of business should be to placate them with either feasts, gifts, or outright force if you have to. Also, make sure to keep them as powerless as possible so that they cannot rise against you in the first place.
I'll have to try and see f I can get Crusader Kings to run in Linux somehow :D
karnak1: I think CK2 has more options considering liege/vassal relationships than the first game (I've never played 2 so I wouldn't know).
In CK1 your relationship with your vassals will gradually increase with time (if you're a good ruler, that is). The trouble is that, as soon as you have a new king, almost 80% of your vassals (from the lowest count to the grandest duke) will become grumpy and suspicious towards you. And the only option the game gives you to appease them is:
a) fill their pockets with gold
b) grant them titles (most of the times you'll only be creating a more powerful rival)
c) wait for them to become so discontent that they'll try to break free from you. Than you can fight them and crush them. But, if such a thing happens, there's a very high risk that you'll provoke a civil war (since all the other grumpy vassals will try to break free as well).
The fact is that your vassals will absolutely adore your king. And then (in the blink of an eye) they will absolutely hate his heir. Which is a bit extreme and not really very realistic IMHO.
Anyway, thanks for the help, Judas.
Any more tips?
If you have to grant titles, grant titles to people that are desired by other people, perhaps transfer a vassal who desires a given title to a powerful vassal of yours in order to give them someone to deal with within their own ranks.
I am not sure if traits are involved in CK1 but maybe your vassals are unhappy because of your new sire's traits? If so, remove those vassals who don't like your new liege's traits and install vassals that are compatible with your new liege.
(my advice is based on CK2 as I cannot get Ck1 to play nicely under Mint for some reason :/ )