Postgresql moving external joining tables into single table

I have inherited a schema that was generated using an ORM tool (Hibernate) which uses lots of joining tables for storing system notifications, works fine except that the SELECT notifications query has now become a major bottleneck as it requires so many joins. I have decided that merging these joining tables into the notifications table (as nullable FK's) is the way to go, this will allow me to index the FK's to improve SELECT performance

Current scheme:

create table notifications(
    notification_id serial primary key,
    date_created timestamp not null default now(),
    title_id text not null,
    message_id text not null
);

create table notifications_user(
    user_id integer references users,
    notification_id integer references notifications,
    primary key(user_id, notification_id)
);

create table notifications_client(
    client_id integer references clients,
    notification_id integer references notifications,
    primary key(client_id, notification_id)
);

Target Scheme:

create table notifications(
    notification_id serial primary key,
    date_created timestamp not null default now(),
    title_id text not null,
    message_id text not null,
    user_audience integer references users,
    client_audience integer references clients,
);

Problem:

I am able to add the extra column but the UPDATE query took over an hour to run (table has ~300k rows)

ALTER TABLE notifications ADD COLUMN user_audience integer references users;
UPDATE notifications as n SET n.user_audience = (SELECT user_id FROM notifications_user WHERE notification_id = n.notification_id);
ALTER TABLE notifications ADD COLUMN client_audience integer references clients;
UPDATE notifications as n SET n.client_audience = (SELECT client_id FROM notifications_clients WHERE notification_id = n.notification_id);

I tried going down the route of creating a new table from scratch, populating and then renaming the old one, but there are lots of other FK references to notifications so this would be difficult

There is only one index on notifications (on the PK)

Any advice on how to improve performance?

PostgreSQL 9.0