Theo Đại nam thực lục, Tổng đốc Yên Hà Nguyễn Công Nhàn và Tuần phủ An Giang Nguyễn Công Trứ không ưa nhau. Nguyễn Công Trứ trước đó là Tham tán cầm quân, còn Nguyễn Công Nhàn xuất thân là tì tướng (lĩnh binh).

Khi Nguyễn Công Trứ làm Tuần phủ An Giang thì Nguyễn Công Nhàn làm Tổng đốc An Hà (An Giang, Hà Tiên), tức là ở địa vị trên. Nguyễn Công Trứ vì thế lấy làm bất bình. Nguyễn Công Nhàn đoán biết được tâm trạng ấy nên tìm cách ngầm hại. 

Trong lúc Nguyễn Công Trứ đi xem xét công việc khơi sông, viên Đề đốc Quang Mật phát hiện đội trưởng coi bến Châu Giang là Mai Văn Thạch tự tiện cho 4 chiếc thuyền buôn lậu chèo đi.

Nguyễn Công Nhàn cùng Phùng Nghĩa Phương tra xét việc ấy, kết luận rằng chiếc thuyền trên được Nguyễn Công Trứ phái người đi thăm dò ở xứ Trấn Tây, nhân cơ hội đó để buôn sừng tê giác và đậu khấu. Nguyễn Công Nhàn tâu lên vua. 

Vua sai Tham tri bộ Lễ Trần Ngọc Dao cùng Lại khoa Chưởng ấn là Đặng Kham đi đến ngay để tra xét. Ngọc Dao biết được vụ việc do Nguyễn Công Nhàn vu cáo, bèn kết án tâu rằng: Phùng Nghĩa Phương và Nguyễn Công Nhàn mắc tội vu cáo, xin phạt trượng và đày đi xa. Còn Nguyễn Công Trứ làm việc sơ suất nên phạt trượng và cách chức.

Nguyễn Công Trứ thành anh lính canh giữ biên giới. Ảnh minh họa.

Vua dụ rằng: Nguyễn Công Nhàn xuất thân từ lúc làm tì tướng, lên đến chức trọng trấn một địa phương, chưa từng làm nên được việc gì. Trước kia, cái án hối lộ ở thôn Tân Hựu phát ra, ta đã châm chước xử nhẹ theo luật; nay còn không biết lo một lòng với nhau giúp nước, để che cái lỗi trước, lại còn cố ý vu cáo cho người khác, gây nên một vụ án lớn. Đáng lẽ theo như án đã nghĩ xử, phạt tội đày đi xa để răn những kẻ theo ý riêng mà bỏ việc công. Nhưng nghĩ Công Nhàn năm trước đánh lui được giặc ở đất Sa Tôn, lập công ở sông Vĩnh Tế. Chiếu theo luật điều đối với người có công, ta cũng có thể giảm nhẹ, vậy gia ân cho cách chức, gắng sức làm việc chuộc tội.

Với Nguyễn Công Trứ, vua phán: Trước phái đi biên giới phía Tây, giao cho việc quân rất quan trọng, lâu ngày không làm nên công trạng gì, ta cũng bỏ qua cho, lại cho làm Tuần phủ An Giang. Tuy rằng, việc thuyền buôn chở đồ gian là do người khác bịa đặt nhưng xét ra việc đó cũng là “mượn công làm tư”, tội tình không thể che giấu được. Nguyễn Công Trứ bị phái đi biên thùy tỉnh Quảng Ngãi...

Lúc đến tỉnh Quảng Ngãi, vào chào quan tỉnh để đợi lệnh đi đồn nào, ông mặc cái áo cộc màu chàm, đầu đội nón dấu. Quan Tổng đốc sở tại thấy tình cảnh một người từng là Thượng thư nay thất thế đến mức như vậy thì tỏ ra rất áy náy, muốn cho phép ông cởi đồ lính ra. Nhưng Nguyễn Công trứ nói: Xin cứ để vậy. Lúc làm đại tướng tôi không lấy làm vinh, nay làm lính tôi cũng không thấy làm nhục. Người ta ở địa vị nào, có nghĩa vụ đối với địa vị ấy, làm lính mà không mang đồ ấy thì sao gọi là lính được.

Câu trả lời này khiến viên quan đầu tỉnh càng thêm kính phục Nguyễn Công Trứ.

Có lẽ vì hiểu lòng liêm khiết của ông nên một năm sau đó, năm Thiệu Trị 5 (1845), vua cho Nguyễn Công Trứ được khởi phục làm Chủ sự bộ Hình, quyền Viên ngoại lang; rồi lại đổi quyền Viên ngoại lang Đại lý tự. 

Châu bản triều Nguyễn cho biết, năm Thiệu Trị 6 (1846), Nguyễn Công Trứ được bổ tạm quyền Án sát Quảng Ngãi. Tháng 9 năm đó, ông được bổ thụ Phủ thừa phủ Thừa Thiên.

Đây không phải là lần duy nhất Nguyễn Công Trứ bị vu cáo, nhưng với phẩm chất liêm khiết, lối sống thanh sạch, lần nào ông cũng vô can. Mặc dù bị vu cáo và vô can vì lúc đó đang “đi xem xét việc khơi sông”, chứ cũng không phải là “ngồi yên không quan tâm việc gì” nhưng ông vẫn không tránh khỏi bị mắc tội. Đó cũng là một trong những chuyện kỳ lạ trớ trêu trong cuộc đời làm quan đầy thăng trầm của ông.

Trước đó đã có nhiều việc chứng minh lòng thanh sạch của ông, vua Minh Mạng cũng rất hiểu nhân cách con người ông nên khi ông xin về lo việc tang (năm 1826), vua cho 100 lạng bạc. Năm Minh Mạng thứ 13 (1832), ông được thăng làm Lang trung Nội vụ, sau đó được bổ Bố chánh Hải Dương. Lúc ông đi nhậm chức, vua Minh Mạng có dụ rằng: “Khanh nhà nghèo, trẫm vẫn biết rõ, nay ra tân lị, cứ giữ lòng thanh liêm như thế, nếu chi dụng không đủ, thì mật tâu về trẫm sẽ chu cấp cho”.

Đến tỉnh lị được hai tháng, ông túng bấn trong tiêu pha, mật tấu về, vua sai thị vệ đem cho hai chục bánh thuốc, trà, mỗi bánh ở trong có một nén bạc.