static void 
operation_spec_unref (OperationSpec *os) 
{
  os->ref_count--;
<snip>
static void 
operation_spec_ref (OperationSpec *os) 
{
  GRL_DEBUG ("Reffing spec");
  os->ref_count++;
<snip>

This stuff is horrible, and really not thread-safe. Use a GBoxed instead if you really need refcounting.

(This might be responsible for this crash:
==31263== Invalid read of size 8
==31263==    at 0x6FF0035: g_type_check_instance_is_fundamentally_a (gtype.c:4026)
==31263==    by 0x6FD19E6: g_object_unref (gobject.c:3067)
==31263==    by 0x6CB0C66: complete_in_idle_cb_for_thread (gsimpleasyncresult.c:835)
==31263==    by 0x7257BA2: g_main_dispatch (gmain.c:3125)
==31263==    by 0x7257BA2: g_main_context_dispatch (gmain.c:3750)
==31263==    by 0x7257FA7: g_main_context_iterate.isra.29 (gmain.c:3821)
==31263==    by 0x72582C1: g_main_loop_run (gmain.c:4015)
==31263==    by 0x5055964: gtk_main (gtkmain.c:1208)
==31263==    by 0x40C323: main (main.c:2433)
==31263==  Address 0x2a11c830 is 32 bytes inside a block of size 72 free'd
==31263==    at 0x4C2ACE9: free (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
==31263==    by 0x725D75E: g_free (gmem.c:190)
==31263==    by 0x7274453: g_slice_free1 (gslice.c:1112)
==31263==    by 0x6FEEEA5: g_type_free_instance (gtype.c:1941)
==31263==    by 0x1E8F3079: operation_spec_unref.part.3 (grl-youtube.c:474)
==31263==    by 0x1E8F4560: operation_spec_unref (grl-youtube.c:960)
==31263==    by 0x1E8F4560: search_cb (grl-youtube.c:966)
==31263==    by 0x6CB0BCC: g_simple_async_result_complete (gsimpleasyncresult.c:763)
==31263==    by 0x6CB0C58: complete_in_idle_cb_for_thread (gsimpleasyncresult.c:832)
==31263==    by 0x7257BA2: g_main_dispatch (gmain.c:3125)
==31263==    by 0x7257BA2: g_main_context_dispatch (gmain.c:3750)
==31263==    by 0x7257FA7: g_main_context_iterate.isra.29 (gmain.c:3821)
==31263==    by 0x72582C1: g_main_loop_run (gmain.c:4015)
==31263==    by 0x5055964: gtk_main (gtkmain.c:1208)
==31263==    by 0x40C323: main (main.c:2433)
)