The rewrite test failed

Hello

I've tried to solve the following error message through many ways - including setting persmission, etc - but still getting the same message.

Error Message during Install: "The rewrite test failed and the most likely cause is that AllowOverride is not set to All for Elgg's directory....."

Elgg: 1.8.1
Host: Arvixe

Has anyone found the solution for this problem?