Is there a limit for the attachment size in Messages?
Despite Joost's links, Apple did officially provide a size limit for Messages attachments.

Extracted from Mountain Lion's Features page:


  Send large attachments: Send high-quality photos, full HD video, or documents. iMessage allows attachments of up to 100MB.


Your 36MB file is, indeed, off the limit.