Holy christ, so many wrong answers here.
Anyway, from anyone coming in from Google like I did and reading through the nonsense above (with the exception of one or two posts): The crappy Android "Mail" app has a hard-limit of 5MB, it simply won't let you attach any files over that size. It's...