Problem with ‘post__not_in’

You are trying to supply an array as part of the string query parameter. You could instead just supply the arguments list as an array like this:

$newQuery = new WP_Query( 
    array( 
        'posts_per_page' => 5, 
        'orderby' => 'rand', 
        'cat' => $cats[0]->term_id, 
        'post__not_in' => array($exclude_post)
    )
);