Ah but here is the problem.
To you, removing a virus from Linux is easy, because you are obviously an intelligent Linux user.
(Someone posted above the removal instructions)
For you to write out: sudo rm -f /usr/bin/Auto.bash /usr/bin/run.bash /etc/profile.d/gnome.sh index.php run.bash && sudo dpkg -r app5552
seems like nothing at all, but what about the average computer user? Do you think they know what sudo is? Hell I don't use Linux and I have no idea what the shit any of that stuff means. So no, that would only work with someone who really knows what they are doing with Linux.
Now on the flip side, you say...
"On Windows and the like, things are so complicated that Anti-virus software is almost required to remove some of their malware"
Ah, but this is going off the assumption that we are dealing with an average Windows user, not an expert user (Such as your self with Linux)
An expert Windows user like myself would say "Removing Malware is easy, just go into the registry's run section, remove what looks suspicious, delete temp files, prefetch, and search for the malware running process (Example: virus.exe) in the registry, and delete it"
Ah see that to me is easy, I've done things like that all the time, and it's just cake.
So I guess the point I'm trying to make is that...To you, removing a virus like this from Linux can be really simple...to someone who knows Linux, but the same can be said to a Windows user...who knows about Windows.