I've noticed that amarok is randomly removing entire albums from my collection.

I've even re added the folder and it still ends up disappearing.

Any ideas on how to fix this?

I had the same problem using Amarok under Suse 10.2 and now under Kubuntu fiesty.  I just reorganized some music (using the Amarok organize files feature) and the files that were organized have now disappeared from the database, but are perfectly well organized on the disk as they should be.  The interesting thing is that this is true for all but one album, which resided on a different disk.