There isn't a copyright notice. Should I try to get a hold of the user to ask them to release it under CC0 or should I remove the attribution since the code is so simple?

We're not using his original code anymore, with the changes I requested.

It does:

In [1]: from django.db.models.query import Q

In [2]: parts = ['parts[0]', 'parts[1]']

In [3]: q = 'q'

In [4]:query = (
   ...:    (Q(first_name__istartswith=parts[0]) &
   ...:     Q(last_name__istartswith=parts[1])) |
   ...:    (Q(first_name__istartswith=parts[1]) &
   ...:     Q(last_name__istartswith=parts[0]))
   ...:)

In [5]: str(query)
Out[5]: "(OR: (AND: ('first_name__istartswith', 'parts[0]'), ('last_name__istartswith', 'parts[1]')), (AND: ('first_name__istartswith', 'parts[1]'), ('last_name__istartswith', 'parts[0]')))"

In [6]: query |= (Q(first_name__istartswith=q) | Q(last_name__istartswith=q))

In [7]: str(query)
Out[7]: "(OR: (AND: ('first_name__istartswith', 'parts[0]'), ('last_name__istartswith', 'parts[1]')), (AND: ('first_name__istartswith', 'parts[1]'), ('last_name__istartswith', 'parts[0]')), ('first_name__istartswith', 'q'), ('last_name__istartswith', 'q'))"

In [8]: query &= Q(profile__is_private=False)

In [9]: str(query)
Out[9]: "(AND: (OR: (AND: ('first_name__istartswith', 'parts[0]'), ('last_name__istartswith', 'parts[1]')), (AND: ('first_name__istartswith', 'parts[1]'), ('last_name__istartswith', 'parts[0]')), ('first_name__istartswith', 'q'), ('last_name__istartswith', 'q')), ('profile__is_private', False))"

No. The way that Q works is that it builds a tree of nodes. Each operator makes a new tree with the operator at the root and the expressions on the LHS and RHS of the tree.
If I put this into the intial query we would get:
((big_first_query) & Q(profile__is_private=False)) | (Q(first_name__istartswith=q) | Q(last_name__istartswith=q))
Which is not the same.