They should not be cemented. If its been a while since its been
removed, use a channel lock or pipe wrench. Worst case you could always
cut it and put a new U-trap in.