The initial problem I saw was that you are saying that the message's parent is always itself, you need to specify an additional unsigned integer to relate on. Here's one example:
public function parent(){
return $this->belongs_to('Message', 'parent_id')
}
You need to use that same 'parent_id'
for the children as well:
public function children(){
return $this->hasMany('Message', 'parent_id');
}