Query running slow for only one specific id. (Postgres 9.3) version

Postgresql 9.3 Version

Guys
Here is the issue that I'm facing for couple of weeks now. I have table (size 7GB)

If I run this query with this specific registration id it is using the wrong execution plan and takes more than a minute to complete. Total number of rows for this registration_id is only 414 in this table

explain analyze SELECT max(last_update_date) AS last_update_date FROM btdt_responses WHERE registration_id = 8718704208 AND response != 4;
QUERY PLAN
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Result (cost=2902.98..2903.01 rows=1 width=0) (actual time=86910.730..86910.731 rows=1 loops=1)
InitPlan 1 (returns $0)
-> Limit (cost=0.57..2902.98 rows=1 width=8) (actual time=86910.725..86910.725 rows=1 loops=1)
-> Index Scan Backward using btdt_responses_n5 on btdt_responses (cost=0.57..6425932.41 rows=2214 width=8) (actual time=86910.723..86910.723 rows=1 loops=1)
Index Cond: (last_update_date IS NOT NULL)
Filter: ((response <> 4) AND (registration_id = 8718704208::bigint))
Rows Removed by Filter: 52145434
Total runtime: 86910.766 ms

Same query with any other registration id will come back in milli seconds

explain analyze SELECT max(last_update_date) AS last_update_date FROM btdt_responses WHERE registration_id = 8688546267 AND response != 4;
QUERY PLAN
----------------------------------------------------------------------------------------------------------------------------------------------
Aggregate (cost=529.75..529.78 rows=1 width=8) (actual time=19.723..19.723 rows=1 loops=1)
-> Index Scan using btdt_responses_u2 on btdt_responses (cost=0.57..529.45 rows=119 width=8) (actual time=0.097..19.689 rows=72 loops=1)
Index Cond: (registration_id = 8688546267::bigint)
Filter: (response <> 4)
Rows Removed by Filter: 22
Total runtime: 19.769 ms

Please let me know what I can do to fix this issue.

Thanks