Install the libxine-extracodecs using Adept or from the command line:

sudo aptitude install libxine-extracodecs amarok-engines

Real Media .rm and .ram streams should now work, but, with one catch: The sound sometimes crackles. To fix this do the following:

Setting^_[menu] -> Configure Amarok^{_{[menu item]}} -> Engine  and change the output plug-in to oss.

Thats it!