777 is fine if you're testing and debugging, but 755 is really better.
FlieTYPE is not irrelevant. WP throws some fun errors when you use certain file types. It normally tells you that you're not allowed to upload that type, but sometimes it balks and throws the generic error.
File Size, similarly, should throw a decent error about ... well file size You should be able to handle 40mb with that setup.
What flavor of PHP are you running?