in one case we had to change the column for the clustered index. we have queries that select over 1 million rows in some cases with a one column in the where condition. first we had the clustered index on the PK which was just a random number and a non-clustered on the column in the where condition. big improvement and the threshold from a seek to a scan went from around 1.5 million rows to over 7 million.
in other cases we have a few db's that have been around for over 10 years and upgraded all the way from sql 6.5. on a few tables we would get strange issues where it would do an index scan. same query on the subscriber would be a seek. so we drop all the stats on the publisher and rebuild all indexes and then all is fine