I'm running Debian unstable (via kanotix) and I have the same issue.
Kanotix comes with 3.4, but I upgraded to 3.5 soon after install, and I'm also missing the Extract options. I have the compress menu entries.
Is there an easy way to get them back? I have kdeaddons and kdeutils installed.
Very strange, there is a new option now to "preview in Archiver", which seems to embed Ark into the file manager. This is better than opening files in Ark - rar files for example. KDE doesn't allow you to enter a rar file as a folder like you can with gz or zip files. Anyway, when I open a rar with Ark, I can't drag the files out without silly clipboard errors, but when I choose 'preview in Archiver', I can actually drag them out, which is an improvement...
Still, I would much prefer just to be able to right-click on a rar file and select, "Extract here".