Postgres ON DELETE Rule Not Working With WHERE Clause

I'm trying to implement "Soft Deletes" given the following schema:

CREATE TABLE categories(
  id serial not null primary key,
  num integer,
  "name" text,
  deleted_at timestamp default null
);

CREATE OR REPLACE RULE delete_categories AS
  ON DELETE TO categories
  WHERE old.deleted_at IS NULL
  DO INSTEAD
    UPDATE categories SET deleted_at = NOW()
    WHERE categories.id = old.id;

The expected behavior is that if I try to delete a record with a NULL deleted_at value, it will instead be set to the current timestamp. If I try to delete a record with a non-NULL deleted_at value, it will be deleted normally.

Instead, running the below sequence returns no records, instead of a record with a timestamp in the deleted_at column:

insert into sams_space_dev.cats(num,name,deleted_at) values(9999,'Test Category',null);
delete from sams_space_dev.cats;
select * from sams_space_dev.cats;

It appears as though the RULE does not get triggered at all, and the record is simply deleted, whereas if I modify the RULE by commenting out the WHERE clause, the record is updated as expected but I am barred from being able to delete it fully:

CREATE OR REPLACE RULE delete_categories AS
  ON DELETE TO categories
  -- WHERE old.deleted_at IS NULL
  DO INSTEAD
    UPDATE categories SET deleted_at = NOW()
    WHERE categories.id = old.id;

insert into sams_space_dev.cats(num,name,deleted_at) values(9999,'Test Category',null);
delete from sams_space_dev.cats;
select * from sams_space_dev.cats;

Results:

+----+------+---------------+----------------------------+
| id | num  |     name      |         deleted_at         |
+----+------+---------------+----------------------------+
|  3 | 9999 | Test Category | 2015-03-03 20:05:44.660208 |
+----+------+---------------+----------------------------+