We tried ANALYZE TABLE first, before even submitting the bug report, did not help.

Here's more information about the table structure:
mysql> SELECT type, COUNT(type) FROM suggestion GROUP BY type;
+--------+-------------+
| type   | COUNT(type) |
+--------+-------------+
| user   |    12954761 |
| group  |    12431541 |
| board  |     1395314 |
| newbie |    11091696 |
| dating |     4094086 |
+--------+-------------+
5 rows in set (4 min 52.40 sec)

mysql> SELECT rejected, COUNT(rejected) FROM suggestion GROUP BY rejected;
+----------+-----------------+
| rejected | COUNT(rejected) |
+----------+-----------------+
| y        |         1725700 |
| n        |        40241894 |
+----------+-----------------+
2 rows in set (4 min 38.46 sec)

mysql> SELECT flags, COUNT(flags) FROM suggestion GROUP BY flags;
+-------+--------------+
| flags | COUNT(flags) |
+-------+--------------+
|     0 |     41959046 |
|     1 |         8152 |
|     2 |          567 |
|     3 |           99 |
+-------+--------------+
4 rows in set (9 min 39.81 sec)

mysql> select count(*) from suggestion where user_id=7723036;
+----------+
| count(*) |
+----------+
|      143 |
+----------+
1 row in set (0.01 sec)

mysql> show keys from suggestion;
+------------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| Table      | Non_unique | Key_name | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment |
+------------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| suggestion |          0 | PRIMARY  |            1 | user_id     | A         |     1322871 |     NULL | NULL   |      | BTREE      |         |               |
| suggestion |          0 | PRIMARY  |            2 | type        | A         |     4703541 |     NULL | NULL   |      | BTREE      |         |               |
| suggestion |          0 | PRIMARY  |            3 | obj_id      | A         |    42331875 |     NULL | NULL   |      | BTREE      |         |               |
| suggestion |          1 | user_id  |            1 | user_id     | A         |     1175885 |     NULL | NULL   |      | BTREE      |         |               |
| suggestion |          1 | user_id  |            2 | rejected    | A         |     1209482 |     NULL | NULL   |      | BTREE      |         |               |
| suggestion |          1 | type     |            1 | type        | A         |           2 |     NULL | NULL   |      | BTREE      |         |               |
| suggestion |          1 | type     |            2 | created     | A         |     3848352 |     NULL | NULL   |      | BTREE      |         |               |
| suggestion |          1 | rejected |            1 | rejected    | A         |           2 |     NULL | NULL   |      | BTREE      |         |               |
| suggestion |          1 | rejected |            2 | type        | A         |         938 |     NULL | NULL   |      | BTREE      |         |               |
| suggestion |          1 | rejected |            3 | created     | A         |     4703541 |     NULL | NULL   |      | BTREE      |         |               |
+------------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
10 rows in set (0.00 sec)

There are usually only a few items, betwen 100 and 200 per user_id, so an access by user_id is always the best strategy if it's known and static, like in that case.

The funny thing about that bug is, according to the original query plan trace I posted above, the query planner KNOWS that the cost of using the type index is vastly higher than the cost for the other index - and chooses it anyway - as if the "low_limit" recheck code does not compare the original cost against its cost again and assumes, that an optimization for low LIMITS is always best.