Performance degraded after shrinking
edit:
Will delete this shortly or update based on answer to question. Realized OP mentioned he DID rebuild indexes already.  

Shrinking a SQL Server database causes the data to get massively fragmented due to how the algorithm works.  You'll want to usually presize so you don't have to shrink but don't have to worry about growths too much either.  Always easier to grow a live DB with IFI than to shrink and reindex.

Paul Randal has a great post about this in depth here.  You will want to reindex and check your fragmentation prior and after using this script ripped off here:

SELECT dbschemas.[name] as 'Schema', 
dbtables.[name] as 'Table', 
dbindexes.[name] as 'Index',
indexstats.alloc_unit_type_desc,
indexstats.avg_fragmentation_in_percent,
indexstats.page_count
FROM sys.dm_db_index_physical_stats (DB_ID(), NULL, NULL, NULL, NULL) AS indexstats
INNER JOIN sys.tables dbtables on dbtables.[object_id] = indexstats.[object_id]
INNER JOIN sys.schemas dbschemas on dbtables.[schema_id] = dbschemas.[schema_id]
INNER JOIN sys.indexes AS dbindexes ON dbindexes.[object_id] = indexstats.[object_id]
AND indexstats.index_id = dbindexes.index_id
WHERE indexstats.database_id = DB_ID()
ORDER BY indexstats.avg_fragmentation_in_percent desc