It's been a while since I've played with lilo, but it seems like using "other" isn't what you want to do. Other is something of a catch-all for OS's that need special care. For instance, if you install MS Windows in a partition other than your first one, you have to monkey around with Lilo like crazy to get it to boot correctly.
For a Linux installation, you should be able to use "normal" Lilo commands to get it to run happily. One hint that makes it easier is to load your "rescue" disk, then read the lilo/grub instructions off that, applying them to your situation as needed.
As far as partition magic goes, it's a nice program. However, if it doesn't do what it says (in this case, boot your OS), perhaps it's time to use that support number. That's why you bought it, because if you wanted to work on it yourself you would have just used grub or lilo.
Aside from that, you simply need to tell your bootloader where all the good stuff is, namely the kernel and the device drivers.