How can I improve this query
First, since you already have a UNIQUE index that contains the user_id, you should be able to get rid of the id field, and use the UNIQUE index as the PRIMARY KEY:

CREATE TABLE `twitter_relationships` (
  `user_id` int(11) NOT NULL,
  `source_twitter_id` bigint(20) NOT NULL,
  `target_twitter_id` bigint(20) NOT NULL,
  `relationship_status` tinyint(1) NOT NULL,
  `status_change_date` int(11) unsigned DEFAULT NULL,
  PRIMARY KEY (`user_id`,`source_twitter_id`,`target_twitter_id`),
  KEY `target_status_and_change_date_index`
    (`user_id`,`target_twitter_id`,`relationship_status`,`status_change_date`),
  KEY `user_id_index` (`user_id`,`status_change_date`)
) ENGINE=InnoDB AUTO_INCREMENT=116597775 DEFAULT CHARSET=latin1
PARTITION BY HASH (user_id) PARTITIONS 1000;


Unfortunately, while this removes an index, it may increase storage requirements, due to the way that InnoDB indexes data. See "How Secondary Indexes Relate to the Clustered Index" in http://dev.mysql.com/doc/refman/5.6/en/innodb-table-and-index.html

Second, while the source_and_target index has two of the three fields in your WHERE clause, MySQL will have to do an additional read to find the relationship_status.

Therefore, to improve performance, create an index that includes all three fields in your WHERE clause:

CREATE INDEX user_source_status ON twitter_relationships
    (`user_id`,`source_twitter_id`,`relationship_status`);


Then, if MySQL doesn't use this index automatically, you can force using it, with:

SELECT target_twitter_id 
 FROM `twitter_relationships` FORCE INDEX (user_source_status)
WHERE (`twitter_relationships`.`user_id` = ? 
   AND `twitter_relationships`.`source_twitter_id` = ?
   AND `twitter_relationships`.`relationship_status` = ?) 
LIMIT ?, ?


Lastly, you're missing the UNSIGNED attribute on the id, user_id, source_twitter_id, and target_twitter_id fields. I'm guessing these fields will never store negative values, so it would make sense to make them UNSIGNED.